LeetCode 1 · Arrays & Hashing

Two Sum, explained with a picture

The coat check counter.

EasyArrays & Hashing
▶ Watch it step by step

The problem

Given a list of numbers and a target, find the positions of two numbers that add up to the target. Exactly one such pair exists.

Input:  nums = [3, 8, 5, 9, 4], target = 17
Output: [1, 3]   (8 + 9 = 17)

Picture it

Think of a coat-check counter. Each arriving guest carries a number. Before hanging their coat, the attendant asks: “is there already a coat here whose number is exactly what this guest needs to reach the target?” If yes, those two guests are the pair. If not, the coat goes on the rack. The rack is a dictionary that maps number → position, so the check takes one glance instead of searching every coat.

How to recognise it

  • You need two items that combine (add up, differ by) to a given value.
  • The question asks for positions or existence, so you can stop at the first match.
  • The input is not sorted and you must return original positions, so sorting would lose the indices.
  • n up to 10^4 or more rules out checking every pair; one pass is expected.
  • Once you fix x, the partner is fully determined (target − x). "The partner is known exactly" is the strongest hint for a dictionary lookup.

Start with brute force

Try every pair of positions (i, j) with i < j and check whether the two numbers add up to the target. It is correct and easy to write.

def two_sum_brute(nums, target):
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

There are n(n − 1)/2 pairs, so time is O(n²) and extra space is O(1). With n = 10^4 that is about 5 × 10^7 pair checks; with n = 10^5 it is about 5 × 10^9, far too slow for a typical time limit.

From brute force to the idea

  1. Find the waste. For each i, the inner loop scans the rest of the list for one specific value, target − nums[i], searching from scratch every time.
  2. Turn the search into a lookup. A dictionary (Python's hash map) answers "is this value here?" in O(1) on average. So remember the numbers you have already passed.
  3. Look backwards, not forwards. Walk the list once. For x at position i, compute need = target − x. If need is in the dictionary, its stored position and i are the pair. Every pair is found when its second member arrives.
  4. Store after checking. Only then store x → i. Checking first stops a lone 3 pairing with itself when the target is 6.

This is the key idea: the partner is target − x, and a dictionary of what you have seen finds it in O(1).

The key idea

For each number x, the partner you need is target − x. Store what you have seen in a dictionary and look the partner up in O(1).

Python solution

def two_sum(nums, target):
    seen = {}  # coat rack: number -> ticket
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:
            return [seen[need], i]
        seen[x] = i
    return []

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(n²): every pair is checked onceO(1): only two loop indices
Dictionary (shown code)O(n): one pass, each lookup and insert is O(1) on averageO(n): in the worst case every number is stored before the pair appears

Edge cases

  • Empty list or one number: returns []. The problem promises a pair, so this only matters if you reuse the function.
  • Duplicates that form the answer ([3, 3], target 6): returns [0, 1]; the first 3 is stored before the second is checked.
  • Using one number twice ([3, 4], target 6): correctly returns [].
  • Negatives and zero ([-3, 4, 3, 90], target 0): returns [0, 2].
  • Very large values: Python integers do not overflow. In Java or C++, target - x can overflow near the integer limits.
  • Several valid pairs ([1, 2, 3, 4], target 5): returns [1, 2], the pair whose second member comes first, not [0, 3].

Common mistakes

  • Inserting x before checking for its partner, which lets a single 3 "pair" with itself for target 6.
  • Sorting first to use two pointers, then returning positions from the sorted list instead of the original one.
  • Storing position → number instead of number → position, so the lookup is by the wrong key.
  • Searching the dictionary's values (need in seen.values()), which is O(n) per lookup and brings back O(n²).
Your turn: count the pairs

Given a list of numbers and a target, return how many pairs of positions i < j have nums[i] + nums[j] == target. Numbers can repeat, so [2, 2, 2] with target 4 has 3 pairs. Describe your approach, then write it if you like.

Compare with our answer

Keep the same one pass, but the dictionary now stores how many times each number has been seen so far. When x arrives, every earlier copy of target − x forms a new pair with it, so add that count, then record x.

from collections import defaultdict

def count_pairs(nums, target):
    seen = defaultdict(int)   # number -> how many times seen so far
    pairs = 0
    for x in nums:
        pairs += seen[target - x]
        seen[x] += 1
    return pairs

count_pairs([2, 2, 2], 4) is 3 and count_pairs([1, 5, 3, 3, 3], 6) is 4. Time O(n), space O(n).

A strong answer mentions: storing counts instead of positions, adding the count before incrementing (so a number never pairs with itself), and why this is still O(n).

Check what stuck

1. You must find two positions in an unsorted list whose numbers differ by exactly k. Which approach fits best?

2. Why is the shown solution O(n) time rather than O(n²)?

3. A learner moves seen[x] = i above the if need in seen: line. Which input now gives a wrong answer?

Score 60% or more and the lesson is marked complete.