How to Approach a DSA Problem

Most people fail these problems by starting to type. The thinking is the work; the code is the easy part once the thinking is done.

The method

1. Restate the problem in your own words, out loud. Half of all wrong answers are answers to a different question.
2. Write down one example by hand, including an awkward one - empty input, one element, duplicates.
3. Solve it the obvious slow way. A working brute force beats an elegant idea you cannot finish.
4. Name the bottleneck. Which step repeats work? That is the only part worth improving.
5. Improve just that step, usually by trading memory for time.

Worked through

Given an array of numbers and a target, return the two indices that add up to the target.

Step 3, the obvious way - try every pair:

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

console.log(twoSum([2, 7, 11, 15], 9))  // [0, 1]

It works. On 10,000 numbers it does about 50 million comparisons.

Step 4 - the bottleneck is the inner loop. For each number we search the whole array for its partner. We already know what the partner is: target - nums[i]. We just cannot find it quickly.

Step 5 - that is exactly what a hash map is for:

function twoSum(nums, target) {
  const seen = new Map()

  for (let i = 0; i < nums.length; i++) {
    const partner = target - nums[i]
    if (seen.has(partner)) return [seen.get(partner), i]
    seen.set(nums[i], i)
  }

  return []
}

console.log(twoSum([2, 7, 11, 15], 9))  // [0, 1]

One pass instead of nested loops. The idea did not come from cleverness - it came from naming which step was slow.

The trade you keep making

The fast version stores every number it has seen. That is more memory for less time, and it is the single most common trade in this whole subject. When you are stuck, ask: what could I remember that would save me from looking again?