Algorithms · interview field notes

Two Sum: the partner you've already seen

Find the two indices whose values add to a target. The brute-force answer is obvious and O(n²); the famous one trades a little memory for a single pass and O(n). The whole leap is one reframe — stop hunting for pairs, start remembering what you've passed.

given nums, targetreturnbecause

[2,7,11,15], t=9[0,1]2 + 7 = 9

[3,2,4], t=6[1,2]2 + 4 = 6

[3,3], t=6[0,1]3 + 3 = 6

Exactly one valid answer exists, and you may not reuse the same element twice. Return the indices, in any order.

The brute force is two nested loops — what exactly is it recomputing on every pass?

A hash map turns the inner loop into a single lookup. What does it store, and when?

The honest first idea

Try every pair

Two nested loops: fix a number, test it against every later number, stop when a pair hits the target. It always works — and on a long array, it's slow. Watch where the effort goes.

Brute force · check every pair

sum = nums[i] + nums[j] ?= 9

The honest first idea: try every pair. Fix one number with i, then walk j across everything to its right, adding the two and checking against the target 9.

01 / 07

For each of n numbers we may scan the whole rest of the array — about n²/2 comparisons. The deeper waste: every inner loop is just searching for one specific value, from scratch, over and over.

The reframe

Every number has one partner

The fix isn't a faster search — it's not searching at all. The partner a number needs is completely determined, so the only real question is whether we've met it yet.

The trick · one partner each

x▼

needs 9 − 7 = ?

Forget pairs for a second. Pick one number — say nums[1] = 7. How many other numbers could possibly complete it?

01 / 04

The whole idea

For a number x, its partner must be target − x — there is no other option. So replace "search the array for it" with "have I already seen it?", and make that question instant.

One pass

Remember as you go, in a hash map

Walk the array once. At each number, ask the map for its complement; if it's there, you're done; if not, drop the current number into the map and keep walking. Every lookup and insert is O(1).

Hash map · one pass, O(n)

complement = 9 − nums[i]

seen · value → index

{ } empty

One pass, left to right, carrying a hash map of every value we've already passed → its index. Start empty.

01 / 05

Say this

"I keep a map of value → index for everything I've passed. At each step I look up target − nums[i]. A hit gives me both indices immediately; a miss just files the current number for someone later. One pass, because the answer is always behind me."

The payoff

n² versus n

Same problem, two costs. Brute force re-searches; the hash map remembers. On a 10,000-element array that's the difference between ~50 million comparisons and ~10,000.

brute force · O(n²) time · O(1) space

Two pointers, no extra memory. Fine for tiny inputs or when you truly can't allocate — but the work explodes as the array grows.

hash map · O(n) time · O(n) space

One pass. Spend O(n) memory on the map of seen numbers and the inner search vanishes — the canonical interview answer.

the whole solution · javascriptO(n) time · O(n) space

function twoSum(nums, target) {

    const seen = new Map();                 // value -> index

    for (let i = 0; i < nums.length; i++) {

        const need = target - nums[i];      // the only partner that works

        if (seen.has(need))                 // already walked past it?

            return [seen.get(need), i];     // done — one pass

        seen.set(nums[i], i);               // remember this one

}

}

Check before you store, and the "can't reuse an element" rule is handled for free — at index i the map holds only earlier indices.

The one-liner to land

"Each number's partner is target − x, fully determined — so I don't search, I remember. One pass with a value→index map: look up the complement, return on a hit, otherwise store and continue. O(n) time for O(n) space."