Two Sum

A strong Two Sum solution replaces repeated pair scanning with one sharper question: has the array already shown us the value this number needs?

The Core Idea: Look Up the Complement

Given an integer array nums and an integer target, return the indices of two different elements whose values add up to target. The problem guarantees exactly one valid answer, and the indices may be returned in either order.

The elements must be different positions, but they do not need to have different values. For example, [3, 3] with target 6 is valid because the two 3s occur at indices 0 and 1.

For a current value nums[i], the missing partner is deterministic:

complement = target - nums[i]

That turns pair search into a lookup problem. Instead of repeatedly scanning the rest of the array, remember values already seen and the indices where they occurred. The hash map becomes a memory indexed by value; the current number asks it for one specific key.

Recognition rule: If a problem asks whether a value needed by the current element has appeared earlier, consider a hash map that stores the required lookup key and its useful payload.

Two Sum does not depend on sorted input, so sorting and two pointers are not the natural first move. The leverage comes from keyed memory: trade O(n) extra space for a one-pass, O(n) average-time search.

Start with the Brute-Force Baseline

The direct solution checks every pair of distinct indices:

def two_sum_brute(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]

This is a useful baseline, not wasted work. Starting j at i + 1 examines every unordered pair once and prevents an element from pairing with itself. The algorithm is correct because any valid answer must appear among those pairs.

Its cost is the problem. For n values, the nested loops perform up to n(n - 1) / 2 comparisons, which is O(n²) time. The extra space is O(1), excluding the input.

The optimization should preserve the same obligation—find two indices whose values sum to the target—while removing the repeated scan.

Derive the One-Pass Algorithm

Scan the array from left to right. Maintain a map called seen with this invariant:

Before processing index i, seen maps values from earlier indices to one of their earlier indices.

For the current num, there are two cases:

1. target - num is already in seen. The stored index and i form the answer.
2. The complement is absent. No earlier value can pair with num, so record num and i for a later element.

The order matters: check first, then insert.

Suppose num == 3 and target == 6. At the first 3, the complement is also 3. If you inserted before checking, the value could match its own index and produce an invalid pair such as [i, i]. Checking only the processed prefix makes every successful match use two distinct positions.

This gives each piece of state a clear job:

• complement identifies the exact value required to complete the sum.
• seen stores the earlier values that may satisfy that requirement.
• The map’s value is an index because the problem asks for positions, not just numbers.

The code is short because the invariant does the heavy lifting.

Python Implementation

def two_sum(nums, target):
    seen = {}

    for i, num in enumerate(nums):
        complement = target - num

        if complement in seen:
            return [seen[complement], i]

        seen[num] = i

Read each iteration as three verbs:

1. Compute the missing partner.
2. Search the earlier prefix for that partner.
3. If it is absent, remember the current value and index.

The function returns as soon as it finds the pair. The supplied contract guarantees one solution, so continuing would only do unnecessary work. If you reuse this pattern for a different problem that allows no solution, define the fallback behavior explicitly; it is outside this contract.

Dry Run: Watch the Map Become Useful

Take nums = [2, 7, 11, 15] and target = 9:

Index	Value	Complement	seen before lookup	Action
0	2	7	{}	Store 2: 0
1	7	2	{2: 0}	Return [0, 1]

At index 1, the current value is 7, so it needs 2. The map already remembers that 2 appeared at index 0. The answer is assembled from the old index and the current index.

Now use the duplicate case:

nums = [3, 3]
target = 6

The first 3 finds no earlier complement and is stored as {3: 0}. The second 3 finds that entry and returns [0, 1]. Equal values are allowed; reusing one position is not.

The map is not a second copy of the array. It is a purpose-built record of the past, shaped around the question the current element needs to ask.

Correctness: Why the Invariant Holds

At the beginning of an iteration, seen contains only values from indices before i.

• If the complement is present, its stored index j satisfies j < i. By definition, nums[j] == target - nums[i], so nums[j] + nums[i] == target. The indices are distinct and the returned pair is valid.
• If the complement is absent, no earlier index can form the target with nums[i]. Storing seen[num] = i extends the remembered prefix for the next iteration.

The invariant therefore remains true after every iteration. Because the problem guarantees a valid pair, the scan eventually reaches an iteration where the complement is present.

This is the difference between a plausible implementation and a proved one: the map is not merely convenient storage. It represents exactly the earlier state required by the next decision.

Complexity and Edge Cases

Each element is processed once. Python dictionary membership and assignment take O(1) time on average, so the algorithm uses:

• Time: O(n) average case
• Extra space: O(n) worst case

The space trade is deliberate. We spend memory to eliminate repeated scanning. If the matching pair appears near the end, the map may hold nearly every previous value.

Important cases to verify:

• Two elements: The first is stored; the second can find its complement.
• Duplicate values: [3, 3] with target 6 returns two different indices.
• Zeroes: [0, 0] with target 0 works because the second zero finds the first.
• Negative values: In [-3, 4, 3, 90] with target 0, the 3 at index 2 finds -3 at index 0.
• Negative target: target - num still directly computes the required value; no special branch is needed.
• No solution: The supplied problem contract excludes this case, so the function does not need to invent a sentinel return value.

When debugging, inspect the state rather than staring at the return line. For a small input, trace i, num, complement, and seen. Read the error, trace the state, fix the assumption. That habit transfers well beyond this coding interview Two Sum problem.

The Transferable Pattern

Two Sum teaches a durable move for arrays and hashing: identify what the current state needs, then ask whether earlier work has already recorded it.

Here, the key is a number and the payload is its index. In another problem, the payload might be a count, a first position, a running total, or a grouped collection. The reusable derivation is:

1. Name the missing partner or required state.
2. Decide what earlier information must be remembered.
3. Check that memory before updating it.
4. State the invariant that makes a hit correct.

My interview rule is simple: derive the invariant before polishing the syntax. Once you can explain what the map remembers, why lookup precedes insertion, and why the cost changes from quadratic to linear average time, the implementation is mostly transcription. The real skill is recognizing when memory can replace a scan.