VFlash: Fast, Accurate Visual Planning via Flash Primitive Decoding
u_Unrolled
DSA for AI/ML · Module 00: The method and Big-O

Lesson 0.6 of 6 in this moduleFree

Two Sum, the six steps out loud

The most-asked interview problem, done the way strong candidates do it: clarifying questions, a brute force, two optimisations derived from first principles, tests against the brute force, complexity, and five follow-ups where a changed constraint changes the answer.

about 15 min 7 Python examples 2 quick checks

Two Sum is the most frequently asked coding problem there is, and that's exactly why it's useful: the interviewer already knows the answer, so they're grading how you get there. This lesson runs the full six-step loop on it, out loud, from the clarifying questions to the follow-ups. Every step builds on lessons 0.1 to 0.5: hidden costs, constraints, memory trade-offs and the right Python structures.

The problem. Given a list of integers nums and an integer target, return the indices of two different elements whose values add up to target.

text
nums = [3, 8, 1, 6, 4], target = 10   →   (3, 4)    because 6 + 4 = 10

ML context. The core idea, "look up the complement in a hash map", is the hash join at the heart of data pipelines: matching training rows to labels by key, joining feature tables on user ID, finding pairs of items whose costs fit a budget exactly.


1. Step 1: Clarify

Say these questions out loud; each one changes the code or the algorithm.

Question Typical answer Why you asked
Is there always exactly one solution? Yes (classic version) If not: return what? None? All pairs?
Can I use the same element twice? No [3], target 6 must not return (0, 0)
Can values repeat? Yes [3, 3], target 6 → (0, 1) is valid
Negative numbers? Zero? Yes Rules out tricks that assume positives
Return indices or values? In what order? Indices, any order Sorting loses original indices unless you keep them
How large is n? Up to 10⁴ (classic), follow-up: 10⁵+ Decides whether O(n²) is acceptable
Is the input sorted? No Sorted input unlocks a different solution

Constraint arithmetic: at n = 10⁴, n²/2 = 5 × 10⁷ pair checks: a few seconds in Python, borderline. At n = 10⁵ it's 5 × 10⁹: far too slow. So expect to optimise, and say so.


2. Step 2: Brute force

Try every pair (i, j) with i < j.

for nums [3, 8, 1, 6, 4] and target 10, the brute force checks pairs in order and only finds 6 + 4 = 10 at the tenth and last pair.
Diagram— for nums [3, 8, 1, 6, 4] and target 10, the brute force checks pairs in order and only finds 6 + 4 = 10 at the tenth and last pair.
python
def two_sum_brute(nums, target):
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):           # j > i: different elements, each pair once
            if nums[i] + nums[j] == target:
                return (i, j)
    return None


assert two_sum_brute([3, 8, 1, 6, 4], 10) == (3, 4)
assert two_sum_brute([3, 3], 6) == (0, 1)
assert two_sum_brute([3], 6) is None        # can't reuse the single 3
assert two_sum_brute([-2, 7, 11, 5], 3) == (0, 3)
print("brute force works")
  • Correctness: every pair is checked, so if a valid pair exists, it's found. j > i prevents reusing an element.
  • Time: n(n − 1)/2 checks in the worst case: O(n²).
  • Space: O(1).
  • Verdict against the constraints: fine for n ≤ a few thousand; too slow at 10⁵. Optimise.

3. Step 3: Optimise, from first principles

What is the brute force really doing? For each nums[i], it searches the rest of the list for one specific value: target − nums[i], the complement. Searching a list is O(n). So the question becomes: how do I find a specific value faster than scanning? There are two classic answers: order (sorting) and hashing.

Optimisation 1: sort, then walk two pointers inward

If the values were sorted, we could start with the smallest and the largest:

  • If their sum is too small, the smallest value can't be part of any solution with anything (the largest partner is already too small), so move the left pointer right.
  • If the sum is too big, the largest value is too big for every partner, so move the right pointer left.
  • If it equals the target, done.

Each step discards one value forever, so the walk takes at most n steps. Sorting loses the original positions, so we sort (value, original index) pairs.

sorted values [1, 3, 4, 6, 8] with original indices; the pointers move from the ends: 1 + 8 = 9 too small, 3 + 8 = 11 too big, 3 + 6 = 9 too small, 4 + 6 = 10 found at original indices 4 and 3.
Diagram— sorted values [1, 3, 4, 6, 8] with original indices; the pointers move from the ends: 1 + 8 = 9 too small, 3 + 8 = 11 too big, 3 + 6 = 9 too small, 4 + 6 = 10 found at original indices 4 and 3.
python
def two_sum_sorted_pointers(nums, target):
    pairs = sorted((v, i) for i, v in enumerate(nums))   # O(n log n); keeps original indices
    left, right = 0, len(pairs) - 1
    while left < right:
        total = pairs[left][0] + pairs[right][0]
        if total == target:
            i, j = pairs[left][1], pairs[right][1]
            return (min(i, j), max(i, j))
        if total < target:
            left += 1                                   # need a bigger sum
        else:
            right -= 1                                  # need a smaller sum
    return None


assert two_sum_sorted_pointers([3, 8, 1, 6, 4], 10) == (3, 4)
assert two_sum_sorted_pointers([3, 3], 6) == (0, 1)
assert two_sum_sorted_pointers([3], 6) is None
print("sort + two pointers works")
  • Time: O(n log n) to sort + O(n) to walk = O(n log n).
  • Space: O(n) for the (value, index) pairs.
  • Why it's correct: a value is discarded only when it cannot be in any solution with the remaining values, so we never skip the answer.

Optimisation 2: one pass with a hash map

The two-pointer version still pays O(n log n) for sorting. Can we find the complement in O(1)? Yes: remember every value we've seen, with its index, in a dict. For each new value x, check whether target − x is already there.

scanning [3, 8, 1, 6, 4] with target 10; the map grows 3:0, 8:1, 1:2, 6:3, and at index 4 the needed complement 6 is found at index 3, giving (3, 4).
Diagram— scanning [3, 8, 1, 6, 4] with target 10; the map grows 3:0, 8:1, 1:2, 6:3, and at index 4 the needed complement 6 is found at index 3, giving (3, 4).
python
def two_sum_hash(nums, target):
    seen = {}                                 # value -> index where we saw it
    for j, x in enumerate(nums):
        need = target - x
        if need in seen:                      # O(1) average
            return (seen[need], j)
        seen[x] = j                           # store AFTER checking: never pair x with itself
    return None


assert two_sum_hash([3, 8, 1, 6, 4], 10) == (3, 4)
assert two_sum_hash([3, 3], 6) == (0, 1)      # second 3 finds the first
assert two_sum_hash([3], 6) is None           # single 3 can't pair with itself
assert two_sum_hash([0, 4, 3, 0], 0) == (0, 3)
print("one-pass hash map works")
  • Time: one pass, O(1) average per step: O(n).
  • Space: O(n) for the map.
  • The subtle line: storing x after checking means an element can never pair with itself, which handles [3] with target 6, while [3, 3] still works because the second 3 finds the first.

Quick check

In the one-pass hash map, why is seen[x] = j placed after the need in seen check rather than before?

  1. It's faster
  2. Storing first would let x find itself when target = 2x, wrongly pairing an element with itself
  3. Python requires it
  4. It saves memory
Show the answer

B. Storing first would let x find itself when target = 2x, wrongly pairing an element with itself — Checking before storing guarantees the complement came from an earlier, different index.


4. Step 4: Code cleanly

The hash version is the one to present by default. Its clean form is above; the habits:

  • seen, need, j: names that explain themselves.
  • Return as soon as the answer is known.
  • Handle "no solution" explicitly (return None) even if the problem promises one; say so.

5. Step 5: Test, against the brute force

Random tests can have several valid answers, so test the property (different indices, correct sum) and agreement on whether a solution exists, rather than exact index pairs.

python
import random


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


def two_sum_sorted_pointers(nums, target):
    pairs = sorted((v, i) for i, v in enumerate(nums))
    left, right = 0, len(pairs) - 1
    while left < right:
        total = pairs[left][0] + pairs[right][0]
        if total == target:
            i, j = pairs[left][1], pairs[right][1]
            return (min(i, j), max(i, j))
        if total < target:
            left += 1
        else:
            right -= 1
    return None


def two_sum_hash(nums, target):
    seen = {}
    for j, x in enumerate(nums):
        if target - x in seen:
            return (seen[target - x], j)
        seen[x] = j
    return None


def valid(nums, target, answer):
    if answer is None:
        return True
    i, j = answer
    return i != j and nums[i] + nums[j] == target


edge_cases = [([], 5), ([5], 10), ([5, 5], 10), ([1, 2], 4), ([-3, 3], 0), ([0, 0, 0], 0), ([10**9, -10**9], 0)]
rng = random.Random(9)
random_cases = [([rng.randint(-15, 15) for _ in range(rng.randint(0, 12))], rng.randint(-20, 20)) for _ in range(1000)]

for nums, target in edge_cases + random_cases:
    reference = two_sum_brute(nums, target)
    for fn in (two_sum_sorted_pointers, two_sum_hash):
        got = fn(nums, target)
        assert valid(nums, target, got), (fn.__name__, nums, target, got)
        assert (got is None) == (reference is None), (fn.__name__, nums, target)
print("all versions agree on", len(edge_cases) + len(random_cases), "cases")

6. Step 6: Complexity, and the comparison

a comparison of brute force (O(n²) time, O(1) space, small n), sort with two pointers (O(n log n) time, O(n) space for indices, sorted or memory-tight), and a one-pass hash map (O(n) time and space, the default answer).
Diagram— a comparison of brute force (O(n²) time, O(1) space, small n), sort with two pointers (O(n log n) time, O(n) space for indices, sorted or memory-tight), and a one-pass hash map (O(n) time and space, the default answer).
Approach Time Extra space Use when
Brute force O(n²) O(1) n small; simplest to trust
Sort + two pointers O(n log n) O(n) (indices) input sorted, or memory matters
One-pass hash map O(n) average O(n) the default answer

7. When the constraints change: the follow-ups

Interviewers almost always follow up with a changed constraint. Each one has a crisp answer.

a decision map for Two Sum: brute force for small n, a hash map for the classic version, two pointers for sorted input, sorting in place when memory is tight, a prebuilt count map for many targets, and a counting structure for a stream of adds and finds.
Diagram— a decision map for Two Sum: brute force for small n, a hash map for the classic version, two pointers for sorted input, sorting in place when memory is tight, a prebuilt count map for many targets, and a counting structure for a stream of adds and finds.

Follow-up A: the input is already sorted (return 1-based indices)

Sorting is free, so the two-pointer walk needs no extra memory at all: O(n) time, O(1) space. This beats the hash map on memory.

Trace it by hand before coding, the way you would at the whiteboard, on [1, 3, 4, 6, 8] with target 10: (1, 8) = 9 → move left; (3, 8) = 11 → move right; (3, 6) = 9 → move left; (4, 6) = 10 ✓, 1-based positions 3 and 4. Writing the trace first gives you the expected answer for your test, and catches off-by-one mistakes before they reach code.

python
def two_sum_sorted_input(numbers, target):
    left, right = 0, len(numbers) - 1
    while left < right:
        s = numbers[left] + numbers[right]
        if s == target:
            return (left + 1, right + 1)
        if s < target:
            left += 1
        else:
            right -= 1
    return None


assert two_sum_sorted_input([1, 3, 4, 6, 8], 10) == (3, 4)       # 4 + 6 = 10, from the trace
assert two_sum_sorted_input([2, 7, 11, 15], 9) == (1, 2)
assert two_sum_sorted_input([1, 2], 10) is None
print("sorted-input two pointers works")

Follow-up B: count all pairs (values can repeat)

"How many pairs (i < j) sum to the target?" Now we can't stop at the first match. For each value, the number of earlier values equal to its complement is the number of new pairs it forms, so store counts, not indices.

python
from collections import Counter


def count_pairs(nums, target):
    seen = Counter()
    pairs = 0
    for x in nums:
        pairs += seen[target - x]       # every earlier complement forms a pair with x
        seen[x] += 1
    return pairs


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


import random

rng = random.Random(4)
for _ in range(500):
    nums = [rng.randint(-5, 5) for _ in range(rng.randint(0, 15))]
    t = rng.randint(-6, 6)
    assert count_pairs(nums, t) == count_pairs_brute(nums, t)
assert count_pairs([1, 1, 1, 1], 2) == 6         # C(4, 2)
print("pair counting works: O(n) time, O(n) space")

Follow-up C: memory is very tight and you only need the values

Sort in place (nums.sort()) and walk two pointers: O(n log n) time, O(1) extra (beyond the sort's internals). We trade time for memory.

Follow-up D: many targets, same array

Build a value → count map once (O(n)); each query checks complements with a pass over the distinct values. If the same targets repeat, cache their answers. Precompute once, reuse many times (lessons 0.2 and 0.3).

Follow-up E: a stream of add(number) and find(target) calls

Design a class. Which operation should be cheap depends on the workload, a constraint in its own right:

python
from collections import Counter


class TwoSumStore:
    """add is O(1); find is O(distinct values). Good when adds outnumber finds."""

    def __init__(self):
        self.counts = Counter()

    def add(self, number):
        self.counts[number] += 1

    def find(self, target):
        for x, c in self.counts.items():
            y = target - x
            if y != x and y in self.counts:
                return True
            if y == x and c >= 2:              # the same value twice needs two copies
                return True
        return False


store = TwoSumStore()
for v in (1, 3, 5):
    store.add(v)
assert store.find(4) is True       # 1 + 3
assert store.find(7) is False
assert store.find(2) is False      # only one 1
store.add(1)
assert store.find(2) is True       # now 1 + 1
print("stream design works")

If find were far more frequent than add, you'd flip the trade: keep a set of all pairwise sums on every add (O(n) per add) so each find is O(1). The workload is a constraint.

Follow-up constraint Best answer Time Space
Classic, unsorted One-pass hash map O(n) O(n)
Already sorted Two pointers O(n) O(1)
Count pairs, duplicates Counter of complements O(n) O(n)
Memory tight, values only Sort in place + two pointers O(n log n) O(1)
Stream, many adds Counter; scan on find add O(1), find O(n) O(n)
Stream, many finds Store all pair sums add O(n), find O(1) O(n²)
Three numbers (3Sum) Sort + fix one + two pointers O(n²) O(1)

Quick check

The interviewer asks for all triples summing to zero (3Sum). How does Two Sum's thinking extend?

  1. Sort once, fix each element as the first, then run the sorted two-pointer Two Sum on the rest for the complement: O(n²) instead of O(n³)
  2. Use three nested loops; nothing better exists
  3. Use a hash map of triples: O(n)
  4. Binary search each pair: O(log n)
Show the answer

A. Sort once, fix each element as the first, then run the sorted two-pointer Two Sum on the rest for the complement: O(n²) instead of O(n³) — Reducing a k-sum problem to repeated two-pointer Two Sums is the classic step from O(n³) to O(n²); module 03 covers it.


8. Saying it out loud: the full 45-second script

"Let me confirm: return two different indices, values may repeat or be negative, n up to 10⁴ and possibly 10⁵, input unsorted. Brute force checks every pair: O(n²), up to 5 × 10⁹ at 10⁵, too slow. For each value I'm searching for its complement, so I'll remember values I've seen in a dict from value to index: one pass, O(n) time, O(n) space. I check before inserting so an element can't pair with itself. If the input were sorted, I'd walk two pointers from the ends instead: O(n) time and O(1) space. Let me code the hash version and test duplicates, a single element, negatives and no solution."


Check yourself

  1. Which clarifying questions change the code for Two Sum, and how?
  2. Explain why the two-pointer walk never skips the answer.
  3. Why is seen[x] = j after the check, not before?
  4. Why must random tests check properties rather than exact index pairs?
  5. What changes when the input is sorted? When you must count all pairs? When memory is tight?
  6. In a stream design, how does the add-versus-find ratio change the data structure?
Answers
  1. Reusing an element (store after checking), duplicates ([3, 3]), returning indices (keep indices when sorting), input size (O(n²) or not), sortedness (two pointers with O(1) space), "no solution" (return None).
  2. When the sum is too small, the left value can't reach the target even with the largest remaining partner, so it can't be in any solution; symmetrically for too big. Only impossible values are discarded.
  3. Storing first would let a value find itself when target = 2x.
  4. Several valid pairs can exist, and different algorithms may return different ones; validity and existence are what must agree.
  5. Sorted: two pointers, O(n) time, O(1) space. Counting: store counts of complements, O(n). Memory tight: sort in place and use two pointers, O(n log n) with O(1) extra.
  6. Many adds: keep counts, scan on find. Many finds: precompute all pair sums on add so find is O(1), at O(n) per add and O(n²) space.