Two Sum

Learning goal: Translate Two Sum into a precise search for a pair of distinct indices.

Core idea For each number, there is exactly one value that would complete the target: complement = target - num. The challenge is to find that complement among values already encountered without comparing every possible pair. Because the answer uses two different elements, the current position must never be paired with itself.

Algorithm plan

• Scan nums from left to right.
• For the current value num, compute complement = target - num.
• Search a map from value to its earlier index.
• If the complement exists, return its stored index and the current index.
• Otherwise, store num with its index and continue.

Micro-example For nums = [2, 7, 11, 15] and target = 9, start with 2; its complement is 7, which has not appeared. After storing 2, the next value 7 finds that complement immediately.

Pitfalls

• The result contains indices, not the two values.
• The two indices must be different.
• A hash map lookup is expected to take average O(1) time.

Recap

• Every number determines one required complement.
• Scan once while remembering earlier values.
• Return as soon as the complement is found.

Learning goal: Understand why a value-to-index hash map removes the need to rescan earlier elements.

Core idea When the scan reaches num, every earlier value is already a possible partner. Instead of asking the current value to compare against all of them, compute the one value that would make the sum equal target. The map acts as memory: it answers whether that exact complement has appeared and where.

Data structure model

Use a hash map with this meaning:

For each array position, the map contains only earlier positions. This ordering naturally prevents using the same array element twice.

Micro-example At index 1, num = 7 and target = 9, so complement = 2. The map contains {2: 0}, so the answer is [0, 1].

Pitfalls

• The map stores indices, not just a set of values.
• Do not confuse num with its complement.
• The map represents the processed prefix, not the whole array.

Recap

• target - num is the only candidate partner needed.
• Value-to-index storage makes the lookup direct.
• A left-to-right scan keeps partners distinct.

Learning goal: Write the one-pass algorithm in the order that preserves correctness.

Core idea The crucial order is check first, insert second. At index i, the map should contain candidates from indices before i, but not nums[i] itself. Checking first preserves that invariant and prevents a value from satisfying its own complement lookup.

Algorithm plan

seen = empty map
for i from 0 to nums.length - 1:
    num = nums[i]
    complement = target - num
    if complement is in seen:
        return [seen[complement], i]
    seen[num] = i

The map lookup and insertion are average O(1), so each array element is processed once. Compared with brute force, the tradeoff is additional memory for a large reduction in repeated work.

Micro-example At i = 0, store 2 only after checking for 7. At i = 1, check for 2 before storing 7; the map returns index 0.

Pitfalls

• Inserting before checking can create a self-match, especially when target = 2 * num.
• Returning values instead of indices violates the required output.
• Continuing after a match is unnecessary because the answer is unique.

Recap

• Check the complement first.
• Insert the current value only when no match exists.
• One pass plus a hash map gives O(n) average time.

Learning goal: Trace the map, complement, and answer on one concrete input.

Core idea We will process nums = [2, 7, 11, 15] with target = 9. At every position, the map contains exactly the values from earlier positions. The first successful lookup ends the algorithm, so the remaining values never need to be examined.

Algorithm plan

• Start with an empty map.
• At index 0, inspect 2; its complement is 7.
• Since 7 is absent, record 2 → 0.
• At index 1, inspect 7; its complement is 2.
• Since 2 is present at index 0, return [0, 1].

Micro-example Before index 0: seen = {}. After recording index 0: seen = {2: 0}. At index 1, the lookup for 2 succeeds, producing the pair of indices [0, 1].

Pitfalls

• Do not search for target + num; the equation is num + complement = target.
• Do not add 7 before checking for 2.
• Once a match appears, do not process later values as if the answer were unknown.

Recap

• The map grows only after an unsuccessful lookup.
• The successful lookup at index 1 points back to index 0.
• The trace widget shows the invariant after every action.

Learning goal: Recognize the ordering mistake and test the algorithm against tricky inputs.

Core idea A hash map solution is short, but its correctness depends on what the map means at the moment of lookup. Before checking, it must contain only earlier elements. If the current value is inserted first, the algorithm can incorrectly use the same index twice when the target is twice that value.

Algorithm plan

• Read num and compute complement.
• Check complement in seen.
• Return immediately on a hit.
• Insert num only after a miss.

Micro-example For nums = [3] and target = 6, inserting 3 first would make 3 appear to complement itself. The constraints require two indices, so check-before-insert avoids this invalid match. For [3, 3], the first 3 is stored, and the second 3 correctly finds it.

Pitfalls

• Duplicate values are valid when they occur at different indices.
• Negative numbers work because subtraction still computes the complement correctly.
• Never assume the complement is at a later index; the map only needs earlier values.

Recap

• Map ordering is a correctness invariant, not just an implementation detail.
• Check before insertion prevents self-matches.
• Duplicate and negative values need no special branch.

Learning goal: Explain the performance tradeoff and recognize the reusable hashing pattern.

Core idea The algorithm makes one pass through the array. Each iteration performs an average constant-time hash lookup and, when needed, an average constant-time insertion. The map can hold up to n values, so the method uses linear extra memory to avoid the quadratic pair enumeration of brute force.

Algorithm plan

• Use a value-to-index hash map.
• Perform one complement lookup per element.
• Stop at the first match.
• Account for the map in the space complexity.

Micro-example For four numbers, brute force may inspect several pairs. The hash-map method inspects index 0, stores it, then finds the answer at index 1 without touching indices 2 and 3.

Pitfalls

• Hash-table operations are average O(1), assuming a suitable hash implementation.
• The space bound is not O(1) because the map grows with the input.
• Returning early improves actual work but does not change the worst-case bound.

Recap

• Store what you have seen so each element looks up its complement.
• Check first, then insert.
• Final complexity: O(n) average time and O(n) extra space.