1. Two Sum — DSA Atlas

EasyArrays and HashingHash mapComplement lookup

Two Sum

Given an integer array nums and an integer target, return the indices of the two distinct elements whose values sum to target. Each input has exactly one valid answer, and you may not use the same element twice.

Open official problem prompt ↗

In plain English

Find the two positions in the array whose values add up to a given target, using each position at most once.

Picture it like this

Imagine sorting mail into a wall of pigeonholes labeled by value. For each new letter worth x dollars, you glance at hole labeled target - x; if a letter is already waiting there, you have your pair.

Example

Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Why: nums[0] + nums[1] = 2 + 7 = 9

Constraints

2 <= nums.length <= 10^4-10^9 <= nums[i] <= 10^9-10^9 <= target <= 10^9Exactly one valid answer exists

Pattern lesson

See the pattern, then code

Complement lookup

↗

Arrays and Hashing

Duplicates, frequency counts, grouping, membership tests, or pair lookup.. For a current value x, the only partner that works is target - x. If you remember every value you have already passed (mapped to its index), you can check that partner in O(1) as you go.

New words, made simpleKnow these before the algorithm

Complement: For value x and goal target, the number target - x that would complete the pair.
Hash map: A dictionary giving average O(1) lookup and insertion keyed by value.
One-pass: Solving during a single traversal, checking and inserting in the same loop.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Brute force double loop

Quadratic; too slow as n approaches 10^4 and it repeats work already implied by earlier elements.

Try every pair (i, j) and test whether nums[i] + nums[j] == target.

Time O(n^2)Space O(1)

Best choiceOne-pass hash map

Linear time with a single scan; the standard optimal answer.

Store each value's index as you go and look up target - x for the current value before inserting it.

Time O(n)Space O(n)

The rule we keep true

Invariant

After processing index i, the map contains exactly the values nums[0..i] each mapped to an index where it occurred, so any complement found there refers to an earlier, distinct position.

Why this is correct

Reasoning

The unique pair (a, b) with a < b is discovered when the loop reaches b: at that moment nums[a] was inserted on an earlier iteration, so target - nums[b] = nums[a] is present in the map, yielding the correct indices without reusing an element.

The algorithm in three movesSay these aloud before coding

1Scan the array once, tracking each value and its index in a map

seen = {2: 0}

2At value x, compute the complement target - x

at i=1, x=7, need = 9 - 7 = 2 -> found at 0

3If the complement is already in the map, return its stored index and the current index

return [0, 1]

4Otherwise record x and its index and continue

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

112

153

1 · Readx = 2

2 · AskIs 9 - 2 = 7 in seen?

3 · Update stateseen = {}

4 · ResultNo; store seen[2] = 0

Key takeaway

At index 1 the complement 2 is already recorded, so the pair (0, 1) is returned.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3Initialize the map
seen maps a value to the index where it was last observed.
2
Lines 4-7Check-then-insert loop
For each x, look for its complement first so we never pair an element with itself, then record x.
3
Lines 8Fallback return
Unreachable given the guarantee, but keeps the signature total.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Negative numbers and a negative target (complement arithmetic still holds)
Duplicate values such as [3, 3], target 6 where the two indices differ
Target that never matches — problem guarantees one answer, but the empty return keeps the function total

Common beginner mistakes

Inserting x into the map before checking the complement, which can incorrectly pair an element with itself
Returning the values instead of the required indices
Assuming the array is sorted and reaching for two pointers, which would need an O(n log n) sort and lose original indices

Check your understanding

Why must you test the complement before storing the current value in the map?

Two Sum

Two Sum

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Arrays and Hashing