LC 1. Two Sum

The problem

First Solution - $O(n)$ Time

This was my first crack at it:

function twoSum(nums: number[], target: number): number[] {
  let map = {}
  for (let [idx, num] of nums.entries()) {
    if (map[target - num] >= 0) {
      return [idx, map[target - num]]
    } else {
      map[num] = idx
    }
  }
}

I knew I wanted to avoid nested loops which would've checked each pair of numbers against the target. To avoid that, I exploited the fact that by having one of the numbers, x, and the target, t, the other number needed is the difference, t - x. By storing previously encountered numbers in map, the existence of t - x can be quickly verified. Storing the index of each number as it's value in the map avoids the need to find the index later when returning the answer.

Clean up and Improvements

To clean my first try up, I think something like what I have below is more readable and potentially faster. num.entries might be slower than a for ... in loop. I'll also remove the unnecessary else statement, which seems visually cleaner and is something I saw on another solution. It won't make much difference, but seemed to run slightly quicker. I've stored the difference as difference to be verbose and not repeat the subtraction more than once.

function twoSum(nums: number[], target: number): number[] {
  let map = {}
  for (let idx in nums) {
    let difference = target - nums[idx]

    if (map[difference] >= 0) {
      return [idx, map[difference]]
    }

    map[nums[idx]] = idx
  }
}

Other Variations and Information

Variant using an ES6 Map

The same as the previous solution but instead of using a plain object, it implements the Map type. I included this solution just to practice using Map more, but its conceptually the same.

function twoSum(nums: number[], target: number): number[] {
  let map = new Map()
  for (let idx in nums) {
    let difference = target - nums[idx]

    if (map.has(difference)) {
      return [idx, map.get(difference)]
    }

    map.set(nums[idx], idx)
  }
}

Variant using nested loops - $O(n^2)$ Time

This is less optimal, but it's got a fun quirk to it that's worth explaining. Notice that j is i + 1. This is important to avoid duplicates and pairs that have already been checked. Lastly, this version is a bit nicer for demonstrating the underlying n choose 2 idea that determines the raw time complexity, raw meaning without exploiting the target value to find a complimentary value.

function twoSum(nums: number[], target: number): number[] {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1) {
      if (nums[i] + nums[j] === target) {
        return [i, j];
      }
    }
  }
}