firstprinciples
← All problems

Two Sum

EasyArrayHash mapTwo pointersAdded 6 November 2026
Solve on LeetCode #1 Watch the reel

The problem

You get a list of integers nums and a number target. Exactly two positions in the list hold numbers that add up to target. Return those two positions (indices), not the numbers. You can’t use the same position twice, but two different positions may hold the same value.

For nums = [3, 9, 14, 5, 11, 8, 1] and target = 13, the answer is [3, 5], because nums[3] + nums[5] = 5 + 8 = 13.

The key question

For any number x, its partner is fixed: it must be target − x. So the whole problem comes down to this:

When I’m looking at x, how quickly can I tell whether target − x exists, and where it is?

Each approach below answers that question faster than the one before.

Approach 1: Brute force

Check every pair. For each index i, try every later index j and test whether nums[i] + nums[j] equals target. Starting j at i + 1 means each pair is checked once and an element is never paired with itself.

Try every pair (i, j) with i < j and check whether it adds up to 13.

Variables
target
13
Operations
0
1def two_sum(nums, target):
2    n = len(nums)
3    for i in range(n):
4        for j in range(i + 1, n):
5            if nums[i] + nums[j] == target:
6                return [i, j]
7    return []
Step 1 / 18
Try your own input:
TimeO(n²)
SpaceO(1)

Time. Count the pairs. The first number is paired with n − 1 others, the second with n − 2, and so on: (n−1) + (n−2) + … + 1 = n(n−1)/2. That’s about n²/2. Big-O drops the ½, so this is O(n²). Doubling the input roughly quadruples the work.

Space. Only a few variables (i, j, the sum), however long the list. That’s O(1) extra space.

What it wastes: for every i it searches for target − nums[i] by scanning the rest of the list again, even though it has already seen those numbers.

Approach 2: Sort, then two pointers

If the numbers were sorted, the search could be guided. Put lo at the smallest value and hi at the largest:

Each check permanently rules out one number. One catch: sorting moves numbers around, and we must return original indices, so each value keeps its index with it. The small label under each cell shows it.

The answer needs original indices, so pair each value with its index before sorting.

Variables
target
13
Operations
0
1def two_sum(nums, target):
2    pairs = sorted((v, i) for i, v in enumerate(nums))
3    lo, hi = 0, len(pairs) - 1
4    while lo < hi:
5        s = pairs[lo][0] + pairs[hi][0]
6        if s == target:
7            return [pairs[lo][1], pairs[hi][1]]
8        elif s < target:
9            lo += 1
10        else:
11            hi -= 1
12    return []
Step 1 / 8
Try your own input:
TimeO(n log n)
SpaceO(n)

Time. Two parts:

  • Sorting takes O(n log n) with any good comparison sort.
  • The pointer walk: every step moves lo or hi one place closer, so after at most n − 1 steps they meet. That’s O(n).

Total: O(n log n) + O(n). Big-O keeps only the largest term, so O(n log n).

Space. The (value, index) pairs are a new list of n items: O(n).

What it wastes: it sorts the whole list just to find one pair. Sorting tells us where every number is relative to every other, which is far more than we need.

Approach 3: Hash map, one pass (optimal)

Go back to the key question: does target − x exist? A hash map answers “have I seen this value?” in O(1) on average. Walk the list once. For each x, check whether its partner is already in the map. If not, store x → index so a later number can find it.

We never need a second pass. Whichever number of the pair comes second will find the first one waiting in the map.

Walk left to right, remembering every value already seen and its index.

Variables
target
13
seen (value → index)
empty
Operations
0
1def two_sum(nums, target):
2    seen = {}  # value -> index
3    for i, x in enumerate(nums):
4        need = target - x
5        if need in seen:
6            return [seen[need], i]
7        seen[x] = i
8    return []
Step 1 / 13
Try your own input:
TimeO(n)
SpaceO(n)

Time. One loop over n numbers. Each step does one hash lookup and at most one insert, both O(1) on average. n × O(1) = O(n).

Space. In the worst case (the pair is the last two numbers) almost every value gets stored before the answer is found. That’s up to n − 1 entries: O(n).

The trade-off: we spend O(n) memory to save time, going from O(n²) to O(n). Trading memory for speed like this is one of the most common moves in algorithm design.

Comparing the approaches

Approach Time Space Idea
Brute force O(n²) O(1) Check every pair
Sort + two pointers O(n log n) O(n) Sorted order lets each check rule out one number
Hash map O(n) O(n) Remember what you’ve seen; look the partner up in O(1)

The chart counts the basic operations each approach really performs on its worst-case input, where the pair is the last two numbers. Hover to compare at each size.

Brute forceSort + two pointersHash map (one pass)
05,00010,000816326496128input size noperationsBrute forceSort + two pointersHash map (one pass)
Operations performed on worst-case inputs. Brute force counts pair checks; sort + two pointers counts about n·log₂n sort comparisons plus pointer checks; the hash map counts lookups.
Show as a table
nBrute forceSort + two pointersHash map (one pass)
828318
161207916
3249619132
642,01644764
964,56072896
1288,1281,023128

Common mistakes