Module 02 · Hash Maps, Sets, and Frequency State

011. Two-Sum Indices

Foundation · Download this solution · All solutions and shared helpers

Problem

Return two distinct zero-based indices whose integer values sum to target, or [] if no pair exists. Scan the second index from left to right; if several earlier complements exist, use their earliest index. Do not sort or mutate the input.

Examples

Example 1

two_sum([2, 7, 11, 15], 9)
=> [0, 1]

The second value finds its earlier complement.

Example 2

two_sum([3], 6)
=> []

One position cannot be reused.

Example 3

two_sum([3, 3], 6)
=> [0, 1]

Equal values at distinct positions are legal.

Reveal the worked solution and reasoning

Why this mechanism works

For an incoming value x, a successful earlier partner must equal target-x. Remember earlier values in a dictionary instead of scanning them again. Query before inserting x: otherwise one position could incorrectly supply both terms. Preserving the first stored index makes the tie policy deterministic.

State and boundaries

seen maps a previously consumed value to its first index; j is the proposed second index.

Protocol

Start with an empty dictionary.
Compute target-value.
Return its saved index and j if present.
Otherwise remember the current value only if new.
Return [] on exhaustion.

Visualization

past: {2: 0} | incoming: 7
needed: 9 - 7 = 2
answer: [0, 1]

Python implementation

def two_sum(nums, target):
    seen = {}
    for j, value in enumerate(nums):
        needed = target - value
        if needed in seen:
            return [seen[needed], j]
        seen.setdefault(value, j)
    return []

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

two_sum([2, 7, 11, 15], 9)

L2 two_sum: seen = {}
nums=[2, 7, 11, 15]; target=9; seen={}

L3 two_sum: for j, value in enumerate(nums):
nums=[2, 7, 11, 15]; target=9; seen={}; j=0; value=2

L4 two_sum: needed = target - value
nums=[2, 7, 11, 15]; target=9; seen={}; j=0; value=2; needed=7

L7 two_sum: seen.setdefault(value, j)
nums=[2, 7, 11, 15]; target=9; seen={2:0}; j=0; value=2; needed=7

L3 two_sum: for j, value in enumerate(nums):
nums=[2, 7, 11, 15]; target=9; seen={2:0}; j=1; value=7; needed=7

L4 two_sum: needed = target - value
nums=[2, 7, 11, 15]; target=9; seen={2:0}; j=1; value=7; needed=2

Result: [0, 1]. The second value finds its earlier complement.

two_sum([3], 6)

L2 two_sum: seen = {}
nums=[3]; target=6; seen={}

L3 two_sum: for j, value in enumerate(nums):
nums=[3]; target=6; seen={}; j=0; value=3

L4 two_sum: needed = target - value
nums=[3]; target=6; seen={}; j=0; value=3; needed=3

L7 two_sum: seen.setdefault(value, j)
nums=[3]; target=6; seen={3:0}; j=0; value=3; needed=3

Result: []. One position cannot be reused.

Why the solution is correct

Before the query, seen contains only earlier positions, so a returned pair is distinct and has the required sum. Every possible second index is queried in order, and its complement is found exactly when a partner exists. Thus exhaustion proves no pair exists.

Time and space

O(n) expected time and O(n) auxiliary space under ordinary hash-table assumptions.

Common mistakes

Insert-before-query falsely solves [3] with target 6. Storing values instead of indices cannot satisfy the output contract.

Reasoning card

State: seen maps a previously consumed value to its first index; j is the proposed second index.

Invariant: seen maps earlier values to usable indices.

Decision to rehearse: Query the complement before inserting the current value.

Finish: Return [] on exhaustion

Transfer exercise

Count all index pairs instead of returning one; replace each stored index by an earlier-occurrence count.