Two Sum with Indices

The problem

Given an array of integers and a target, return the indices of two different elements whose values add to the target. Assume exactly one valid pair exists, and do not use the same array element twice.

Constraints that change what “correct” means

The input array contains at least two integers.
Exactly one valid pair exists for the core exercise.
The same index cannot be used twice, even when target = 2 × value.
Return indices, not the values themselves.

Examples: predict before reading the explanation

nums = [2, 7, 11, 15], target = 9

Expected: [0, 1]

At index 1 the value is 7, so its needed complement is 2. Index 0 already stored 2.

nums = [3, 2, 4], target = 6

Expected: [1, 2]

The pair is 2 + 4, not 3 + 3, because there is only one 3 and an index cannot be reused.

Build the mental model first

Think first

Before coding, scan [2, 7, 11, 15] from left to right. When you stand on 7, what single value would prove that a pair exists? If you could remember every value already seen together with its index, could you answer that question immediately?

Need a hint?

For each value x, compute target - x. Check whether that complement was seen earlier. Only after checking should you store x, which naturally prevents using the current index twice.

Trace the state before reading code

Trace input: nums = [4, 1, 6, 3], target = 9. Follow the map as it existed before the current value is stored. That detail is the core correctness invariant.

Step	Index	Value	Needed	Seen before this step	Decision
Start	0	`4`	`5`	`{}`	5 is absent, so remember 4 → index 0.
Continue	1	`1`	`8`	`{4: 0}`	8 is absent, so remember 1 → index 1.
Continue	2	`6`	`3`	`{4: 0, 1: 1}`	3 is absent, so remember 6 → index 2.
Match	3	`3`	`6`	`{4: 0, 1: 1, 6: 2}`	6 is present at index 2, so return [2, 3].

Quick reasoning checks

Answer before expanding the explanation. These checks focus on the invariant behind the algorithm rather than syntax recall.

Why does the single-pass solution check for the complement before storing the current value?

It makes the array sorted automatically.
It prevents the current element from matching itself.
It reduces the hash map to constant space.
It guarantees there are no duplicate values.

Answer: B. Checking first means the map contains only earlier indices. A value can therefore match another occurrence, but never the same array position.

In TypeScript, why is `earlierIndex !== undefined` safer than `if (earlierIndex)`?

Map.get always returns strings.
Index 0 is falsy even though it is a valid index.
undefined means the target is negative.
Truthiness checks are slower than comparisons.

Answer: B. A valid complement may have been stored at index 0. Testing truthiness would incorrectly treat that valid index as missing.

Primary solutions

Python

def two_sum(nums, target):
    seen = {}
    for index, value in enumerate(nums):
        needed = target - value
        if needed in seen:
            return [seen[needed], index]
        seen[value] = index
    raise ValueError("no valid pair")

seen maps a value to an index where that value appeared earlier.
At each element we ask the problem in reverse: which value would complete the target?
We check before inserting the current value, so a single element cannot match itself.
Once the complement exists, the earlier index and current index form the required pair.

Complexity: O(n) expected time and O(n) additional space because each element is processed once and the hash map can store up to n values.

TypeScript

function twoSum(nums: number[], target: number): [number, number] {
  const seen = new Map<number, number>();
  for (let index = 0; index < nums.length; index += 1) {
    const value = nums[index];
    const needed = target - value;
    const earlierIndex = seen.get(needed);
    if (earlierIndex !== undefined) return [earlierIndex, index];
    seen.set(value, index);
  }
  throw new Error('no valid pair');
}

Map stores values already observed and the index that produced each value.
The lookup asks whether the complement was seen before the current position.
Using get() carefully matters because index 0 is valid; testing the returned index by truthiness would incorrectly treat 0 as missing.

Complexity: O(n) expected time and O(n) additional space under normal hash-map behavior.

Compare with a simpler baseline

Brute-force pair checking

Use one loop to choose the first index and a second loop to inspect every later index.

This is a good correctness baseline because it mirrors the requirement directly and uses constant extra space.

Its weakness is repeated comparison: as the array grows, the number of candidate pairs grows quadratically.

Complexity: O(n²) time and O(1) extra space.

Common mistakes

Store the current value before checking its complement

For nums = [3, 2, 4] and target = 6, the first 3 could immediately find itself and return the same index twice.

Return the two values instead of their indices

The contract asks for positions. Correct arithmetic can still produce the wrong API result.

In TypeScript, test the found index with if (earlierIndex)

Index 0 is falsy in JavaScript. Compare against undefined instead so index 0 remains valid.

Test the algorithm, not just the happy path

Case	Input	Expected	Why it matters
Pair at the beginning	`[2, 7, 11, 15], target 9`	`[0, 1]`	Confirms the normal complement path.
Duplicate values	`[3, 3], target 6`	`[0, 1]`	Confirms two distinct indices can hold the same value.
Negative number	`[-4, 8, 5, 12], target 1`	`[0, 2]`	Confirms the complement model is not limited to positive numbers.

Independent practice

Change the contract so the function returns every unique value pair that reaches the target instead of one index pair. Decide how duplicates should behave before coding, then explain how that contract changes your data structures.