Two Sum

New to some of the words above? Open a quick recap. Each takes about two minutes.

Quick recapBig-O in two minutes· 2 min

Big-O says how the work grows when the input grows. n is the input size.

• O(1): the same work for any n. Example: nums[3].
• O(n): work grows with n. One loop over the list.
• O(n²): a loop inside a loop. Double n and the work goes up four times.
• O(n log n): a bit more than O(n). Good sorting costs this.

Space works the same way, for the extra memory a solution uses. The full lesson: My code passed every test, then timed out on the big one.

Quick recapLists and indices· 2 min

A Python list keeps items in order. Each item has a position, called its index, starting at 0.

nums = [12, 35, 7]
nums[0]   # 12
nums[2]   # 7
len(nums) # 3
for i, num in enumerate(nums):  # gives index and value together
    print(i, num)

The full lesson: I reversed the list, but the caller’s list didn’t change.

Quick recapPython dict· 2 min

A dict maps keys to values. Looking up a key takes about one step, however big the dict is. That’s O(1) on average.

seen = {}
seen[35] = 1    # remember: value 35 is at index 1
35 in seen      # True, in about one step
seen[35]        # 1

How it finds a key so fast, and the other ways to use one: My anagram check says aab and abb match.

See the problem

You have a gift card worth exactly 50. The menu prices are 12, 35, 7, 15 and 44. You want to spend all of it on exactly two items.

Which two? Try it in your head before reading on.

You probably found 35 and 15. But how did you search? Most people pick a price and look for a partner. Then pick the next one, and look again.

Define the task

• Input: a list nums and a number target.
• Output: the positions (indices) of two different numbers that add up to target, smaller index first. Return [] if no pair exists.
• Rules: you can’t use the same position twice. Numbers can repeat, and can be negative or zero.

Example: nums = [12, 35, 7, 15, 44], target = 50 gives [1, 3], because nums[1] + nums[3] is 35 + 15 = 50.

Pause and think

⏸ Pause and think

How would you find the pair with pen and paper? How many checks would it take for 1,000 prices?

Give it two minutes with pen and paper before you open a hint.

Hints open one at a time:

Hint 1 of 3

Pick any price. Which exact price would its partner need to be?

Hint 2 of 3

For 35, the partner must be 50 − 35 = 15. So the question becomes: have I already seen 15?

Hint 3 of 3

"Have I seen this value before?" is a lookup. Which Python type answers lookups in about one step?

Understand the idea

Picture reading the menu top to bottom. For each price, you work out its partner and glance at a sticky note of prices you’ve already read. If the partner is on the note, you’re done. If not, you add this price to the note and read on.

★Key insight

Each number needs one exact partner: target − number. So “which pair works?” becomes “have I already seen my partner?” That’s a lookup, and a Python dict does lookups in about one step.

Watch it run. The player stops to ask what happens next. Answer, or press Just show me. You can also type your own numbers below the player.

One pass with a hash map

⤢ Full view

1. 120
2. 351
3. 72
4. 153
5. 444

seen (value → index)

empty

Step 1 of 12. Start with an empty map. We want two numbers that add up to 50.

◀ BackPlayNext ▶Reset Ask me first Show as text

1def two_sum(nums: list[int], target: int) -> list[int]:
2    seen: dict[int, int] = {}  # value -> index
3    for i, num in enumerate(nums):
4        partner = target - num
5        if partner in seen:
6            return [seen[partner], i]
7        seen[num] = i
8    return []

Try your own input

NumbersTargetShow it

Climb the ladder

Three ways to solve it. Each one shows the idea, a walkthrough on the gift card example, the code, its cost, and where it breaks.

Okay

Check every pair

The idea: Try each number with every number after it.

On the gift card: 12 with 35, 7, 15 and 44 (no match). Then 35 with 7, then 35 with 15. That adds up to 50, so return [1, 3]. It took 6 checks.

def two_sum(nums: list[int], target: int) -> list[int]:
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

Time

O(n²)

Space

O(1)

Why

Two loops, one inside the other: about n × n / 2 pairs. Nothing extra is stored.

Where it breaks: speed. With 100,000 prices, that’s about 5 billion pair checks. In Python that takes minutes, not milliseconds. Every number scans the whole rest of the list again.

Better

Sort, then walk two pointers inward

The idea: Sort the values (keeping their original indices), then move one pointer from each end toward the middle.

The waste in Okay: it checks pairs that can’t work. Once the list is sorted, one sum tells you which way to move.

On the gift card: sorted, it’s 7, 12, 15, 35, 44. 7 + 44 = 51 is too big, so move the right pointer left. 7 + 35 = 42 is too small, so move the left pointer right. 12 + 35 = 47, still too small. 15 + 35 = 50. Their original indices are 3 and 1, so return [1, 3].

Two pointers on the sorted values

⤢ Full view

1. 70was 2
2. 121was 0
3. 152was 3
4. 353was 1
5. 444was 4

Step 1 of 10. Sort the numbers, keeping each one's original index: 7, 12, 15, 35, 44.

◀ BackPlayNext ▶Reset Ask me first Show as text

1def two_sum(nums: list[int], target: int) -> list[int]:
2    pairs = sorted((value, i) for i, value in enumerate(nums))
3    lo, hi = 0, len(pairs) - 1
4    while lo < hi:
5        total = pairs[lo][0] + pairs[hi][0]
6        if total == target:
7            return sorted([pairs[lo][1], pairs[hi][1]])
8        if total < target:
9            lo += 1
10        else:
11            hi -= 1
12    return []

Try your own input

NumbersTargetShow it

Highlighted lines are new in this rung.

def two_sum(nums: list[int], target: int) -> list[int]:
    pairs = sorted((value, i) for i, value in enumerate(nums))
    lo, hi = 0, len(pairs) - 1
    while lo < hi:
        total = pairs[lo][0] + pairs[hi][0]
        if total == target:
            return sorted([pairs[lo][1], pairs[hi][1]])
        if total < target:
            lo += 1
        else:
            hi -= 1
    return []

Time

O(n log n)was O(n²)

Space

O(n)was O(1)

Why

Sorting costs O(n log n) and the walk is O(n). The pairs list stores every value with its index.

What changed from the previous rung

def two_sum(nums: list[int], target: int) -> list[int]:
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    pairs = sorted((value, i) for i, value in enumerate(nums))
    lo, hi = 0, len(pairs) - 1
    while lo < hi:
        total = pairs[lo][0] + pairs[hi][0]
        if total == target:
            return sorted([pairs[lo][1], pairs[hi][1]])
        if total < target:
            lo += 1
        else:
            hi -= 1
    return []

Where it breaks: sorting does more work than the question needs. And sorting moves the numbers, so you must carry the original indices along. Forgetting that is a classic bug.

Best

One pass with a hash map

The idea: Remember each number you've seen; for every new number, check whether its partner is already remembered.

The waste in Better: sorting puts everything in order, but we only need one thing: “is my partner here?” A dict answers that without sorting.

On the gift card: 12 needs 38 (not seen, remember 12). 35 needs 15 (not seen, remember 35). 7 needs 43 (not seen, remember 7). 15 needs 35, which we saw at index 1. Return [1, 3]. It took 4 lookups.

Highlighted lines are new in this rung.

def two_sum(nums: list[int], target: int) -> list[int]:
    seen: dict[int, int] = {}  # value -> index
    for i, num in enumerate(nums):
        partner = target - num
        if partner in seen:
            return [seen[partner], i]
        seen[num] = i
    return []

Time

O(n) on averagewas O(n log n)

Space

O(n)

Why

One loop. Each dict lookup and insert takes about one step on average. The map can hold every number.

What changed from the previous rung

def two_sum(nums: list[int], target: int) -> list[int]:
    pairs = sorted((value, i) for i, value in enumerate(nums))
    lo, hi = 0, len(pairs) - 1
    while lo < hi:
        total = pairs[lo][0] + pairs[hi][0]
        if total == target:
            return sorted([pairs[lo][1], pairs[hi][1]])
        if total < target:
            lo += 1
        else:
            hi -= 1
    seen: dict[int, int] = {}  # value -> index
    for i, num in enumerate(nums):
        partner = target - num
        if partner in seen:
            return [seen[partner], i]
        seen[num] = i
    return []

When Best isn’t best: if the input is already sorted and memory is tight, two pointers alone is O(n) time and O(1) space. No sort needed, and no dict.

Write it yourself

Now write it in the page. Press Run tests to check your code. Python runs in your browser, so nothing is sent anywhere. Your code is saved in this browser for next time.

Try the Okay version first: it passes the small tests but fails the speed test. Then make it fast.

Two Sum

Ctrl + Enter runs

def two_sum(nums: list[int], target: int) -> list[int]: # Return the positions of the two numbers that add up to target. # Return [] if there is no such pair. return []

Run testsVisualizeReset codeLoads about 6 MB the first time. Best on Wi-Fi.

1. ○Not run yet: two_sum([12, 35, 7, 15, 44], 50) → [1, 3]
2. ○Not run yet: two_sum([3, 2, 4], 6) → [1, 2]
3. ○Not run yet: two_sum([3, 3], 6) → [0, 1]
4. ○Not run yet: Extra test
5. ○Not run yet: Extra test
6. ○Not run yet: Extra test
7. ○Not run yet: Extra test
8. ○Not run yet: Extra test

Extra tests check tricky cases. You see their input only if they fail.

Try your own input

Arguments, separated by commas as in Python

two_sum()Run onceVisualize

Compare

Rung	Time	Space	Good	Not so good	Use it when
Okay	O(n²)	O(1)	Simple, no extra memory	Far too slow for big lists	The list is tiny
Better	O(n log n)	O(n)	Grows into Three Sum	Sorting moves the indices	The list is already sorted
Best	O(n)	O(n)	Fastest, one pass	Uses memory for the map	Almost always, for Two Sum

How much work is that? Each bar below is one rung at the same input size. Pick a size, or run the race.

Two Sum: steps at n numbers

1. OkayCheck every pair · O(n²)≈ 5,000,000,000 pair checks

2. BetterSort, then two pointers · O(n log n)≈ 1,700,000 sort steps

3. BestOne pass with a hash map · O(n)≈ 100,000 lookups

At n = 100,000, Okay does about 50,000 times more work than Best.

Every bar does the same number of steps per second, so the race shows which rung finishes first. Turn on Log scale to compare the short bars.

Common mistakes and edge cases

!Check before you insert

Look for the partner before adding the current number to the map. If you add it first, [3] with target 6 finds 3 as its own partner and returns [0, 0].

• Repeated numbers: [3, 3] with target 6 must give [0, 1]. Checking first makes this work: the first 3 is stored, and the second 3 finds it.
• Negatives and zero need no special case. [0, 5, 0] with target 0 gives [0, 2].
• No answer: return []. Ask the interviewer what they expect here.
• Sorting loses positions: in the Better rung, sort (value, index) pairs, never the bare values.
• “O(1) on average”: a dict lookup can be slow in rare bad cases. Say “on average” in the interview.

Say it in the interview

Questions to ask first

• Can numbers repeat? Can they be negative?
• Is there always exactly one answer? What if there’s none?
• Do you want the positions or the values? In any order?
• Is the list sorted? Roughly how big is it?

A 60-second walkthrough

“The simple way checks every pair. That’s O(n²). The waste is that each number already tells me its partner: target minus the number. If I keep the numbers I’ve seen in a dict, from value to index, each check takes about one step. So one pass gives O(n) time and O(n) space. I check the dict before inserting, so a number never pairs with itself. I’ll test [3, 3] with target 6 and a list with no answer.”

Likely follow-ups

• The list is sorted? Two pointers: O(n) time, O(1) space.
• Return every pair, not one? Keep counts of each value, and watch out for repeats.
• Three numbers? Sort, then for each number run two pointers on the rest. That’s O(n²). See Three Sum below.
• Numbers arrive one at a time? A class with add(number) and find(target). Decide which one should be fast.

Red flags interviewers notice

• Writing code before asking a single question.
• Pairing a number with itself.
• Saying a dict lookup is “always O(1)”.
• Sorting and then returning positions in the sorted list.

Practice

Four related problems, from easy to hard. Each has hints, tests you can run here, and its own Okay, Better and Best answers. Try before you open them.

1. Pair sum in a sorted list (easy)

The list is sorted from small to large. Return the positions [i, j] (with i < j) of two numbers that add up to target, or [] if there are none. There’s at most one answer.

Example: pair_sum_sorted([1, 3, 4, 6, 9], 12) gives [1, 4], because 3 + 9 = 12.

Hint 1 of 3

The list is sorted. What does the sum of the smallest and largest number tell you?

Hint 2 of 3

If that sum is too small, the smallest number can never be part of the answer. Why?

Hint 3 of 3

Move a pointer from each end. Which one moves depends on whether the sum is too small or too big.

Pair sum in a sorted list

Ctrl + Enter runs

def pair_sum_sorted(nums: list[int], target: int) -> list[int]: # nums is sorted. Return [i, j] with i < j, or [] if no pair adds up to target. return []

Run testsVisualizeReset codeLoads about 6 MB the first time. Best on Wi-Fi.

1. ○Not run yet: pair_sum_sorted([1, 3, 4, 6, 9], 12) → [1, 4]
2. ○Not run yet: pair_sum_sorted([2, 2, 5], 4) → [0, 1]
3. ○Not run yet: pair_sum_sorted([-6, -1, 0, 4], -2) → [0, 3]
4. ○Not run yet: Extra test
5. ○Not run yet: Extra test
6. ○Not run yet: Extra test

Extra tests check tricky cases. You see their input only if they fail.

Try your own input

Arguments, separated by commas as in Python

pair_sum_sorted()Run onceVisualize

Show the Okay, Better and Best answers

Okay

Check every pair

The idea: Ignore the sorting and try every pair.

It works, but it wastes the best clue: the list is sorted.

def pair_sum_sorted(nums: list[int], target: int) -> list[int]:
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

Time

O(n²)

Space

O(1)

Why

A loop inside a loop.

Better

Binary search for each partner

The idea: For each number, binary search the rest of the list for target minus that number.

Sorted data means you can halve the search each step instead of scanning.

Highlighted lines are new in this rung.

from bisect import bisect_left


def pair_sum_sorted(nums: list[int], target: int) -> list[int]:
    for i, num in enumerate(nums):
        partner = target - num
        j = bisect_left(nums, partner, i + 1)  # binary search to the right of i
        if j < len(nums) and nums[j] == partner:
            return [i, j]
    return []

Time

O(n log n)was O(n²)

Space

O(1)

Why

n binary searches, each O(log n). bisect_left does the search.

What changed from the previous rung

from bisect import bisect_left


def pair_sum_sorted(nums: list[int], target: int) -> list[int]:
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    for i, num in enumerate(nums):
        partner = target - num
        j = bisect_left(nums, partner, i + 1)  # binary search to the right of i
        if j < len(nums) and nums[j] == partner:
            return [i, j]
    return []

Best

Two pointers

The idea: Start at both ends; move the left pointer up if the sum is too small, the right one down if too big.

Each step rules out one number, so the pointers meet after at most n steps.

Highlighted lines are new in this rung.

def pair_sum_sorted(nums: list[int], target: int) -> list[int]:
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        total = nums[lo] + nums[hi]
        if total == target:
            return [lo, hi]
        if total < target:
            lo += 1  # need a bigger sum
        else:
            hi -= 1  # need a smaller sum
    return []

Time

O(n)was O(n log n)

Space

O(1)

Why

Each step moves one pointer, so at most n steps. Only two variables.

What changed from the previous rung

from bisect import bisect_left


def pair_sum_sorted(nums: list[int], target: int) -> list[int]:
    for i, num in enumerate(nums):
        partner = target - num
        j = bisect_left(nums, partner, i + 1)  # binary search to the right of i
        if j < len(nums) and nums[j] == partner:
            return [i, j]
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        total = nums[lo] + nums[hi]
        if total == target:
            return [lo, hi]
        if total < target:
            lo += 1  # need a bigger sum
        else:
            hi -= 1  # need a smaller sum
    return []

2. Count pairs with a given difference (medium)

Count the pairs of positions i < j where the two numbers differ by exactly k. k is 0 or more.

Example: count_pairs([1, 5, 3, 4, 2], 2) gives 3: the pairs are (1, 3), (5, 3) and (4, 2).

Hint 1 of 3

For a number x, which two values could its partner be?

Hint 2 of 3

Its partner is x + k or x − k. When k is 0, those are the same value, so count it once.

Hint 3 of 3

Walk the list once with a counter of values seen so far. Each new number adds the counts of its partners.

Count pairs with a given difference

Ctrl + Enter runs

def count_pairs(nums: list[int], k: int) -> int: # Count pairs of positions i < j where abs(nums[i] - nums[j]) == k. return 0

Run testsVisualizeReset codeLoads about 6 MB the first time. Best on Wi-Fi.

1. ○Not run yet: count_pairs([1, 5, 3, 4, 2], 2) → 3
2. ○Not run yet: count_pairs([1, 1, 2], 1) → 2
3. ○Not run yet: count_pairs([7, 7, 7], 0) → 3
4. ○Not run yet: Extra test
5. ○Not run yet: Extra test
6. ○Not run yet: Extra test

Extra tests check tricky cases. You see their input only if they fail.

Try your own input

Arguments, separated by commas as in Python

count_pairs()Run onceVisualize

Show the Okay, Better and Best answers

Okay

Check every pair

The idea: Try every pair and count the ones that differ by k.

Simple and correct, including repeats, but slow for big lists.

def count_pairs(nums: list[int], k: int) -> int:
    count = 0
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if abs(nums[i] - nums[j]) == k:
                count += 1
    return count

Time

O(n²)

Space

O(1)

Why

A loop inside a loop.

Better

Sort, then binary search

The idea: Sort a copy; for each number, count the copies of number + k to its right with two binary searches.

After sorting, every copy of number + k sits in one block to the right, so its size is one subtraction.

Highlighted lines are new in this rung.

from bisect import bisect_left, bisect_right


def count_pairs(nums: list[int], k: int) -> int:
    values = sorted(nums)
    count = 0
    for i, num in enumerate(values):
        # Copies of num + k sit to the right of i once the list is sorted.
        count += bisect_right(values, num + k, i + 1) - bisect_left(values, num + k, i + 1)
    return count

Time

O(n log n)was O(n²)

Space

O(n)was O(1)

Why

Sorting is O(n log n), then n pairs of binary searches. The sorted copy is O(n).

What changed from the previous rung

from bisect import bisect_left, bisect_right


def count_pairs(nums: list[int], k: int) -> int:
    values = sorted(nums)
    count = 0
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if abs(nums[i] - nums[j]) == k:
                count += 1
    for i, num in enumerate(values):
        # Copies of num + k sit to the right of i once the list is sorted.
        count += bisect_right(values, num + k, i + 1) - bisect_left(values, num + k, i + 1)
    return count

Best

One pass with a counter

The idea: Count values as you go; each new number adds how many times its partners were already seen.

The same trick as Two Sum: instead of searching for partners, remember what you’ve seen.

Highlighted lines are new in this rung.

from collections import Counter


def count_pairs(nums: list[int], k: int) -> int:
    seen: Counter[int] = Counter()  # value -> how many times seen so far
    count = 0
    for num in nums:
        if k == 0:
            count += seen[num]
        else:
            count += seen[num - k] + seen[num + k]
        seen[num] += 1
    return count

Time

O(n) on averagewas O(n log n)

Space

O(n)

Why

One loop with dict-like lookups. The counter can hold every value.

What changed from the previous rung

from bisect import bisect_left, bisect_right
from collections import Counter


def count_pairs(nums: list[int], k: int) -> int:
    values = sorted(nums)
    seen: Counter[int] = Counter()  # value -> how many times seen so far
    count = 0
    for i, num in enumerate(values):
        # Copies of num + k sit to the right of i once the list is sorted.
        count += bisect_right(values, num + k, i + 1) - bisect_left(values, num + k, i + 1)
    for num in nums:
        if k == 0:
            count += seen[num]
        else:
            count += seen[num - k] + seen[num + k]
        seen[num] += 1
    return count

3. Three Sum (medium)

Find every different group of three numbers, from three different positions, that adds up to target. Write each group smallest first. The groups can come in any order, but don’t repeat a group.

Example: three_sum([4, -1, 2, -3, 1, 0], 0) gives [[-3, -1, 4], [-3, 1, 2], [-1, 0, 1]].

Hint 1 of 3

Fix the first number. What problem is left for the other two?

Hint 2 of 3

It is Two Sum on the rest of the list. If the list is sorted, two pointers solve it in one pass.

Hint 3 of 3

To avoid repeated groups, skip a first number equal to the one before it, and skip repeats of the second number after a match.

Three Sum

Ctrl + Enter runs

def three_sum(nums: list[int], target: int) -> list[list[int]]: # Return every different group of three numbers that adds up to target, # each group smallest first. return []

Run testsVisualizeReset codeLoads about 6 MB the first time. Best on Wi-Fi.

1. ○Not run yet: three_sum([4, -1, 2, -3, 1, 0], 0) → [[-3, -1, 4], [-3, 1, 2], [-1, 0, 1]]
2. ○Not run yet: three_sum([0, 0, 0, 0], 0) → [[0, 0, 0]]
3. ○Not run yet: three_sum([2, 2, 2, 3, 3], 7) → [[2, 2, 3]]
4. ○Not run yet: Extra test
5. ○Not run yet: Extra test
6. ○Not run yet: Extra test

Extra tests check tricky cases. You see their input only if they fail.

Try your own input

Arguments, separated by commas as in Python

three_sum()Run onceVisualize

Show the Okay, Better and Best answers

Okay

Check every group of three

The idea: Three loops; store each matching group, sorted, in a set to drop repeats.

Correct, but 1,000 numbers already means about 166 million groups.

def three_sum(nums: list[int], target: int) -> list[list[int]]:
    n = len(nums)
    found: set[tuple[int, ...]] = set()
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                if nums[i] + nums[j] + nums[k] == target:
                    found.add(tuple(sorted((nums[i], nums[j], nums[k]))))
    return [list(group) for group in sorted(found)]

Time

O(n³)

Space

O(1) besides the answer

Why

Three loops, one inside the other: about n³ / 6 groups.

Better

Sort, then binary search for the third number

The idea: Sort; for every pair, binary search the rest for target minus the pair.

The innermost loop becomes a binary search, because the list is sorted.

Highlighted lines are new in this rung.

from bisect import bisect_left


def three_sum(nums: list[int], target: int) -> list[list[int]]:
    nums = sorted(nums)
    n = len(nums)
    found: set[tuple[int, ...]] = set()
    for i in range(n):
        for j in range(i + 1, n):
            need = target - nums[i] - nums[j]
            k = bisect_left(nums, need, j + 1)  # binary search for the third number
            if k < n and nums[k] == need:
                found.add((nums[i], nums[j], need))
    return [list(group) for group in sorted(found)]

Time

O(n² log n)was O(n³)

Space

O(n)was O(1) besides the answer

Why

About n² / 2 pairs, each with an O(log n) search. The sorted copy is O(n).

What changed from the previous rung

from bisect import bisect_left


def three_sum(nums: list[int], target: int) -> list[list[int]]:
    nums = sorted(nums)
    n = len(nums)
    found: set[tuple[int, ...]] = set()
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                if nums[i] + nums[j] + nums[k] == target:
                    found.add(tuple(sorted((nums[i], nums[j], nums[k]))))
            need = target - nums[i] - nums[j]
            k = bisect_left(nums, need, j + 1)  # binary search for the third number
            if k < n and nums[k] == need:
                found.add((nums[i], nums[j], need))
    return [list(group) for group in sorted(found)]

Best

Sort, then two pointers for each first number

The idea: Fix the first number, then solve sorted Two Sum on the rest with two pointers, skipping repeats.

Skipping equal neighbours removes repeated groups, so no set is needed.

Highlighted lines are new in this rung.

def three_sum(nums: list[int], target: int) -> list[list[int]]:
    nums = sorted(nums)
    n = len(nums)
    result: list[list[int]] = []
    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # same first number as last time
        lo, hi = i + 1, n - 1
        while lo < hi:
            total = nums[i] + nums[lo] + nums[hi]
            if total < target:
                lo += 1
            elif total > target:
                hi -= 1
            else:
                result.append([nums[i], nums[lo], nums[hi]])
                lo += 1
                while lo < hi and nums[lo] == nums[lo - 1]:
                    lo += 1  # skip copies of the second number
                hi -= 1
    return result

Time

O(n²)was O(n² log n)

Space

O(n)

Why

n first numbers, each with an O(n) two-pointer walk. The sorted copy is O(n).

What changed from the previous rung

from bisect import bisect_left


def three_sum(nums: list[int], target: int) -> list[list[int]]:
    nums = sorted(nums)
    n = len(nums)
    found: set[tuple[int, ...]] = set()
    for i in range(n):
        for j in range(i + 1, n):
            need = target - nums[i] - nums[j]
            k = bisect_left(nums, need, j + 1)  # binary search for the third number
            if k < n and nums[k] == need:
                found.add((nums[i], nums[j], need))
    return [list(group) for group in sorted(found)]
    result: list[list[int]] = []
    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # same first number as last time
        lo, hi = i + 1, n - 1
        while lo < hi:
            total = nums[i] + nums[lo] + nums[hi]
            if total < target:
                lo += 1
            elif total > target:
                hi -= 1
            else:
                result.append([nums[i], nums[lo], nums[hi]])
                lo += 1
                while lo < hi and nums[lo] == nums[lo - 1]:
                    lo += 1  # skip copies of the second number
                hi -= 1
    return result

4. Four Sum (hard)

The same as Three Sum, with groups of four numbers.

Example: four_sum([3, -2, 0, 1, -1, 2], 2) gives [[-2, -1, 2, 3], [-2, 0, 1, 3], [-1, 0, 1, 2]].

Hint 1 of 3

Three Sum fixed one number and ran two pointers. How many numbers do you fix here?

Hint 2 of 3

Fix two numbers with two loops, then run two pointers on the rest.

Hint 3 of 3

Skip repeats at every level: the first number, the second number, and the third after a match.

Four Sum

Ctrl + Enter runs

def four_sum(nums: list[int], target: int) -> list[list[int]]: # Return every different group of four numbers that adds up to target, # each group smallest first. return []

Run testsVisualizeReset codeLoads about 6 MB the first time. Best on Wi-Fi.

1. ○Not run yet: four_sum([3, -2, 0, 1, -1, 2], 2) → [[-2, -1, 2, 3], [-2, 0, 1, 3], [-1, 0, 1, 2]]
2. ○Not run yet: four_sum([2, 2, 2, 2, 2], 8) → [[2, 2, 2, 2]]
3. ○Not run yet: Extra test
4. ○Not run yet: Extra test
5. ○Not run yet: Extra test

Extra tests check tricky cases. You see their input only if they fail.

Try your own input

Arguments, separated by commas as in Python

four_sum()Run onceVisualize

Show the Okay, Better and Best answers

Okay

Check every group of four

The idea: Four loops; store each matching group, sorted, in a set.

Fine for ten numbers; far too slow for a few hundred.

def four_sum(nums: list[int], target: int) -> list[list[int]]:
    n = len(nums)
    found: set[tuple[int, ...]] = set()
    for a in range(n):
        for b in range(a + 1, n):
            for c in range(b + 1, n):
                for d in range(c + 1, n):
                    if nums[a] + nums[b] + nums[c] + nums[d] == target:
                        found.add(tuple(sorted((nums[a], nums[b], nums[c], nums[d]))))
    return [list(group) for group in sorted(found)]

Time

O(n⁴)

Space

O(1) besides the answer

Why

Four loops, one inside the other.

Better

Sort, then binary search for the fourth number

The idea: Sort; for every group of three, binary search for the number that completes it.

The same move as in Three Sum: the innermost loop becomes a binary search.

Highlighted lines are new in this rung.

from bisect import bisect_left


def four_sum(nums: list[int], target: int) -> list[list[int]]:
    nums = sorted(nums)
    n = len(nums)
    found: set[tuple[int, ...]] = set()
    for a in range(n):
        for b in range(a + 1, n):
            for c in range(b + 1, n):
                need = target - nums[a] - nums[b] - nums[c]
                d = bisect_left(nums, need, c + 1)  # binary search for the fourth number
                if d < n and nums[d] == need:
                    found.add((nums[a], nums[b], nums[c], need))
    return [list(group) for group in sorted(found)]

Time

O(n³ log n)was O(n⁴)

Space

O(n)was O(1) besides the answer

Why

About n³ / 6 triples, each with an O(log n) search.

What changed from the previous rung

from bisect import bisect_left


def four_sum(nums: list[int], target: int) -> list[list[int]]:
    nums = sorted(nums)
    n = len(nums)
    found: set[tuple[int, ...]] = set()
    for a in range(n):
        for b in range(a + 1, n):
            for c in range(b + 1, n):
                for d in range(c + 1, n):
                    if nums[a] + nums[b] + nums[c] + nums[d] == target:
                        found.add(tuple(sorted((nums[a], nums[b], nums[c], nums[d]))))
                need = target - nums[a] - nums[b] - nums[c]
                d = bisect_left(nums, need, c + 1)  # binary search for the fourth number
                if d < n and nums[d] == need:
                    found.add((nums[a], nums[b], nums[c], need))
    return [list(group) for group in sorted(found)]

Best

Sort, fix two numbers, then two pointers

The idea: Two loops fix the first two numbers; two pointers find the last two, skipping repeats.

This pattern grows: for groups of k numbers, fix k − 2 of them and finish with two pointers.

Highlighted lines are new in this rung.

def four_sum(nums: list[int], target: int) -> list[list[int]]:
    nums = sorted(nums)
    n = len(nums)
    result: list[list[int]] = []
    for a in range(n - 3):
        if a > 0 and nums[a] == nums[a - 1]:
            continue  # same first number as last time
        for b in range(a + 1, n - 2):
            if b > a + 1 and nums[b] == nums[b - 1]:
                continue  # same second number as last time
            lo, hi = b + 1, n - 1
            while lo < hi:
                total = nums[a] + nums[b] + nums[lo] + nums[hi]
                if total < target:
                    lo += 1
                elif total > target:
                    hi -= 1
                else:
                    result.append([nums[a], nums[b], nums[lo], nums[hi]])
                    lo += 1
                    while lo < hi and nums[lo] == nums[lo - 1]:
                        lo += 1  # skip copies of the third number
                    hi -= 1
    return result

Time

O(n³)was O(n³ log n)

Space

O(n)

Why

About n² pairs of fixed numbers, each with an O(n) walk.

What changed from the previous rung

from bisect import bisect_left


def four_sum(nums: list[int], target: int) -> list[list[int]]:
    nums = sorted(nums)
    n = len(nums)
    found: set[tuple[int, ...]] = set()
    for a in range(n):
        for b in range(a + 1, n):
            for c in range(b + 1, n):
                need = target - nums[a] - nums[b] - nums[c]
                d = bisect_left(nums, need, c + 1)  # binary search for the fourth number
                if d < n and nums[d] == need:
                    found.add((nums[a], nums[b], nums[c], need))
    return [list(group) for group in sorted(found)]
    result: list[list[int]] = []
    for a in range(n - 3):
        if a > 0 and nums[a] == nums[a - 1]:
            continue  # same first number as last time
        for b in range(a + 1, n - 2):
            if b > a + 1 and nums[b] == nums[b - 1]:
                continue  # same second number as last time
            lo, hi = b + 1, n - 1
            while lo < hi:
                total = nums[a] + nums[b] + nums[lo] + nums[hi]
                if total < target:
                    lo += 1
                elif total > target:
                    hi -= 1
                else:
                    result.append([nums[a], nums[b], nums[lo], nums[hi]])
                    lo += 1
                    while lo < hi and nums[lo] == nums[lo - 1]:
                        lo += 1  # skip copies of the third number
                    hi -= 1
    return result

Check yourself

A few quick questions. Ones you miss are remembered, so you can find your weak spots later.

1. Predict the outputWhat does the Best version return?

   two_sum([3, 2, 4], 6)

   [0, 0][1, 2][0, 2][]

   Check answer
2. Spot the bugThis version stores each number before looking for its partner. Which input breaks it?

   def two_sum(nums, target):
       seen = {}
       for i, num in enumerate(nums):
           seen[num] = i
           if target - num in seen:
               return [seen[target - num], i]
       return []

   [2, 7] with target 9[3, 4] with target 6[1, 2, 3] with target 100[] with target 0

   Check answer
3. Multiple choiceWhat is the time cost of the Better rung (sort, then two pointers)?

   O(n)O(n log n)O(n²)O(log n)

   Check answer
4. Pick the patternThe list is already sorted and you may use only a few extra variables. Which approach fits best?

   A dict of values seen so farTwo pointers from both endsCheck every pairSort it again first

   Check answer
5. Fill in the answerFill in the blank: partner = target - ____

   Your answerCheck answer

Flashcards

Add these to your review deck. Each card comes back a little later every time you get it right.

• Card 1Two Sum: what does each number tell you?Show answer
• Card 2Why check the map before inserting the current number?Show answer
• Card 3Time and space of the one-pass hash map?Show answer
• Card 4Input already sorted and memory tight?Show answer
• Card 5How do you extend Two Sum to Three Sum?Show answer

Add 5 cards to my review deck

Cheat sheet

• Need a partner or complement? Keep a dict of the values you’ve seen.
• Sorted input and a pair condition? Two pointers, moving inward.
• Check the dict before you insert the current number.
• Sorting moves items: carry the original index with each value.
• Groups of three or four: sort, fix numbers, finish with two pointers.

Go deeper

• Python dict, from the official docs.
• Time cost of Python operations, from the Python wiki (dict lookups are O(1) on average).
• The bisect module, used in the binary-search answers.
• Next on the DSA roadmap: Two pointers and Sliding window.

Can you do these now?

If you’re not sure of any of these, scroll back to that part before moving on.

• Solve Two Sum three ways and give the time and space of each
• Explain why a hash map turns "check every pair" into one pass
• Choose two pointers instead when the input is already sorted
• Avoid pairing a number with itself, and handle repeated numbers

✓Mark as completeI already know this

Status: Not started