Two Sum with Indices

01 · Predict

Understand the contract before choosing a data structure

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.

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.

Example 1

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.

Example 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.

02 · Trace

Trace the state before reading code

Trace input: nums = [4, 1, 6, 3], target = 9. Read each card as the state before the current value is stored. That timing is the correctness invariant.

01Start

Index: 0
Value: 4
Needed: 5

Seen before{}

5 is absent, so remember 4 → index 0.

02Continue

Index: 1
Value: 1
Needed: 8

Seen before{4: 0}

8 is absent, so remember 1 → index 1.

03Continue

Index: 2
Value: 6
Needed: 3

Seen before{4: 0, 1: 1}

3 is absent, so remember 6 → index 2.

04Match

Index: 3
Value: 3
Needed: 6

Seen before{4: 0, 1: 1, 6: 2}

6 is present at index 2, so return [2, 3].

Reasoning checks

Can you defend the invariant?

2 checks

Answer aloud before expanding each explanation. Syntax is not the test here; the mental model is.

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.

03 · Implement

Translate the same invariant into two languages

Read the explanation after the code and point to the exact line that preserves each claim. If you cannot map reasoning to code, the implementation is still opaque.

Implementation

Python

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.

PythonScroll horizontally if needed

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.

Implementation

TypeScript

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

TypeScriptScroll horizontally if needed

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.

Baseline comparison

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.

Failure patterns

Common mistakes are clues about the wrong mental model

01

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.

02

Return the two values instead of their indices

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

03

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

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

04 · Test

Attack the algorithm, not just the happy path

A passing example only proves one path. These cases are chosen to challenge index identity, duplicates, and the arithmetic assumptions behind the lookup.

Cases that challenge the solution contract
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.

Continue learning

Carry the reasoning somewhere useful

All coding problems →