VFlash: Fast, Accurate Visual Planning via Flash Primitive Decoding
u_Unrolled
DSA for AI/ML · Module 01: Arrays and strings

Lesson 1.3 of 16 in this moduleFree

Two Sum

The complement pattern behind Two Sum, applied to three questions interviewers swap in: the pair sum closest to a target, the largest pair sum below a limit, and pairs with a given difference. Each from brute force to sorted pointers or hashing, and why the change in question changes the tool.

about 15 min 5 Python examples 2 quick checks

Lesson 0.6 solved classic Two Sum end to end: brute force, sorting with two pointers, and a one-pass hash map. This lesson takes the idea underneath (for each value, look for the one specific partner that completes it) and applies it to three variants interviewers commonly substitute. They look almost identical to Two Sum, but each change to the question changes which tool works:

  1. Closest sum: the pair whose sum is closest to a target (no exact match required).
  2. Largest sum below a limit: the biggest pair sum that stays strictly under K.
  3. Pairs with difference k: count distinct pairs whose values differ by exactly k.

If you haven't read lesson 0.6, start there; this lesson assumes its brute force and hash map.


1. The complement pattern

for each value x, the partner question becomes a lookup of target − x in a hash map or in sorted order; the same shape covers pair sums, differences, budget matching and key joins.
Diagram— for each value x, the partner question becomes a lookup of target − x in a hash map or in sorted order; the same shape covers pair sums, differences, budget matching and key joins.

"Find a partner" is a search. Two ways make that search fast:

Tool What it answers fast When it works
Hash map "Is this exact value present?" in O(1) exact matches only
Sorted order "What's near this value?" by moving pointers or binary search exact or approximate, ordered questions

That table is the whole lesson. As soon as a variant asks for something inexact (closest, below, at least), the hash map stops helping, and sorted order takes over.


2. Variant 1: the pair sum closest to a target

Problem. Given n integers and a target, return the sum of two different elements that is closest to the target.

text
nums = [10, 1, 7, 3, 4], target = 12   →   11   (1 + 10 or 4 + 7; 13 = 3 + 10 is equally close)

ML context. Pick two items whose combined cost is as close as possible to a budget; pair two batches whose total token count is closest to a context limit.

Brute force

python
def closest_pair_sum_brute(nums, target):
    best = None
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            s = nums[i] + nums[j]
            if best is None or abs(s - target) < abs(best - target):
                best = s
    return best


assert abs(closest_pair_sum_brute([10, 1, 7, 3, 4], 12) - 12) == 1
print("brute force works")

O(n²) time, O(1) space.

Why the hash map doesn't help

The hash map answers "is target − x present?". Here the ideal partner usually isn't present; we want the nearest one. Hashing destroys order, so "nearest" is invisible to it.

Optimised: sort, then two pointers tracking the best gap

After sorting, the same inward walk as Two Sum works: if the sum is below the target, only a larger left value can get closer; if above, only a smaller right value can. At every step, record the best gap seen.

sorted [1, 3, 4, 7, 10] with target 12: 1 + 10 = 11 (gap 1, best), 3 + 10 = 13 (gap 1), 3 + 7 = 10 (gap 2), 4 + 7 = 11 (gap 1); the pointers meet and the best gap is 1.
Diagram— sorted [1, 3, 4, 7, 10] with target 12: 1 + 10 = 11 (gap 1, best), 3 + 10 = 13 (gap 1), 3 + 7 = 10 (gap 2), 4 + 7 = 11 (gap 1); the pointers meet and the best gap is 1.
python
import random


def closest_pair_sum(nums, target):
    a = sorted(nums)                                   # O(n log n)
    left, right = 0, len(a) - 1
    best = a[0] + a[1]
    while left < right:
        s = a[left] + a[right]
        if abs(s - target) < abs(best - target):
            best = s
        if s == target:
            return s                                   # can't beat an exact match
        if s < target:
            left += 1
        else:
            right -= 1
    return best


def closest_pair_sum_brute(nums, target):
    n = len(nums)
    return min((nums[i] + nums[j] for i in range(n) for j in range(i + 1, n)), key=lambda s: abs(s - target))


rng = random.Random(5)
for _ in range(500):
    nums = [rng.randint(-30, 30) for _ in range(rng.randint(2, 15))]
    t = rng.randint(-60, 60)
    assert abs(closest_pair_sum(nums, t) - t) == abs(closest_pair_sum_brute(nums, t) - t)
print("closest pair: sorted two pointers match brute force")
  • Time: O(n log n) to sort, O(n) to walk. Space: O(n) for the sorted copy (O(1) if sorting in place is allowed).
  • Why it never misses the best pair: when the sum is too small, pairing the left value with anything other than the current right value gives an even smaller sum, so the left value has already been paired with its best partner; discarding it is safe. Symmetrically for too large.
  • Test note: two different pairs can tie (11 and 13 are both 1 away from 12), so the test compares distances, not sums.

3. Variant 2: the largest pair sum strictly below K

Problem. Return the largest nums[i] + nums[j] (i ≠ j) that is less than K, or −1 if none exists.

text
nums = [34, 23, 1, 24, 75, 33, 54, 8], K = 60   →   58   (34 + 24)

ML context. Packing two jobs onto one machine without exceeding memory; choosing two sequences to batch together under a length limit.

Brute force

O(n²): check every pair, keep the best sum below K.

Optimised: sort, two pointers, keep sums that fit

If a[left] + a[right] < K, this pair fits, and it's the best that a[left] can do with anything (every other right partner is smaller). Record it and move left up. Otherwise the sum is too big for a[right] with anything, so move right down.

python
import random


def two_sum_less_than_k(nums, k):
    a = sorted(nums)
    left, right = 0, len(a) - 1
    best = -1
    while left < right:
        s = a[left] + a[right]
        if s < k:
            best = max(best, s)          # fits: the best this left value can do
            left += 1
        else:
            right -= 1                   # too big: this right value can't fit with anything left
    return best


def brute(nums, k):
    n = len(nums)
    return max((nums[i] + nums[j] for i in range(n) for j in range(i + 1, n) if nums[i] + nums[j] < k), default=-1)


assert two_sum_less_than_k([34, 23, 1, 24, 75, 33, 54, 8], 60) == 58
assert two_sum_less_than_k([10, 20, 30], 15) == -1
rng = random.Random(6)
for _ in range(500):
    nums = [rng.randint(1, 50) for _ in range(rng.randint(2, 15))]
    k = rng.randint(1, 100)
    assert two_sum_less_than_k(nums, k) == brute(nums, k)
print("largest sum below K: matches brute force")

Constraint check: if values are small integers (say 1 to 1,000), you can skip sorting with a counting array and walk counts from both ends: O(n + V) instead of O(n log n), the same trade as in lesson 0.3.


4. Variant 3: count distinct pairs with difference k

Problem. Count distinct value pairs (x, y) with y − x = k (k ≥ 0).

text
nums = [1, 2, 4, 6, 9], k = 3   →   2   ((1, 4) and (6, 9))
nums = [1, 1, 1, 2], k = 0      →   1   ((1, 1) counts once)

ML context. Finding events exactly k seconds apart in a log; pairing timestamps across two sensors offset by a known lag.

Brute force

Check every pair, collect distinct (x, y) with y − x = k in a set: O(n²).

Optimisation A: hashing works here (exact match!)

The partner of x is exactly x + k, so a set answers it in O(1). The k = 0 case needs counts: a value pairs with itself only if it appears at least twice.

python
from collections import Counter


def count_k_diff_pairs_hash(nums, k):
    counts = Counter(nums)
    if k == 0:
        return sum(1 for c in counts.values() if c >= 2)
    return sum(1 for x in counts if x + k in counts)      # distinct x only


assert count_k_diff_pairs_hash([1, 2, 4, 6, 9], 3) == 2
assert count_k_diff_pairs_hash([1, 1, 1, 2], 0) == 1
assert count_k_diff_pairs_hash([3, 1, 4, 1, 5], 2) == 2   # (1, 3) and (3, 5)
print("hash version works: O(n) time, O(n) space")

Optimisation B: sorted, both pointers moving right

If memory is tight and sorting in place is allowed, use two pointers that both move right: the difference grows when j advances and shrinks when i advances. (Inward pointers from the ends work for sums, not differences.)

sorted [1, 2, 4, 6, 9] with k = 3; i and j both move right: too small moves j, too big moves i, and matches (1, 4) and (6, 9) are found in six steps.
Diagram— sorted [1, 2, 4, 6, 9] with k = 3; i and j both move right: too small moves j, too big moves i, and matches (1, 4) and (6, 9) are found in six steps.
python
import random


def count_k_diff_pairs_sorted(nums, k):
    a = sorted(nums)
    i, j, count = 0, 1, 0
    n = len(a)
    while j < n:
        if i == j or a[j] - a[i] < k:
            j += 1                                  # difference too small: widen
        elif a[j] - a[i] > k:
            i += 1                                  # too big: narrow
        else:
            count += 1                              # exact match
            x = a[i]
            while i < n and a[i] == x:              # skip duplicates of this x
                i += 1
            j = max(j, i + 1)
    return count


def brute(nums, k):
    n = len(nums)
    return len({(min(nums[i], nums[j]), max(nums[i], nums[j])) for i in range(n) for j in range(n)
                if i != j and abs(nums[i] - nums[j]) == k})


assert count_k_diff_pairs_sorted([1, 2, 4, 6, 9], 3) == 2
rng = random.Random(7)
for _ in range(500):
    nums = [rng.randint(0, 12) for _ in range(rng.randint(2, 12))]
    k = rng.randint(0, 6)
    assert count_k_diff_pairs_sorted(nums, k) == brute(nums, k)
print("sorted fast/slow pointers match brute force")
  • Time: O(n log n). Space: O(1) extra if sorting in place.
  • Duplicates are the trap here: the inner loop skips repeated values of x so each distinct pair counts once.

Quick check

For 'pairs with difference k', why do both pointers move right instead of starting at opposite ends?

  1. It's faster to write
  2. With i < j in sorted order, advancing j increases the difference and advancing i decreases it, so moving both rightward lets you steer the difference; inward pointers steer a sum, not a difference
  3. Inward pointers would skip duplicates
  4. Differences can't be negative
Show the answer

B. With i < j in sorted order, advancing j increases the difference and advancing i decreases it, so moving both rightward lets you steer the difference; inward pointers steer a sum, not a difference — The pointer movement must change the quantity in a predictable direction. For differences, that's a fast/slow walk.


5. Which tool, when: the constraint table

Question Exact match? Best tool Time Space
Sum equals target, return indices Yes Hash map (lesson 0.6) O(n) O(n)
Sum closest to target No Sort + inward pointers O(n log n) O(1) in place
Largest sum below K No Sort + inward pointers O(n log n) O(1) in place
Same, values small (≤ V) No Counting array + two pointers O(n + V) O(V)
Difference equals k Yes Hash set / Counter O(n) O(n)
Difference equals k, memory tight Yes Sort + fast/slow pointers O(n log n) O(1)
Pairs whose sum is in a range [lo, hi] No Sort + count pairs ≤ hi minus pairs < lo O(n log n) O(1)

The pattern: exact questions → hashing; ordered or approximate questions → sorting. Say that sentence in the interview and the choice of tool justifies itself.

Quick check

Count pairs whose sum lies between 10 and 20 inclusive, with n = 10⁵. Which approach fits, and why not a hash map?

  1. Sort, then count pairs with sum ≤ 20 and subtract pairs with sum ≤ 9, each with an O(n) two-pointer pass; a hash map only answers exact sums, and a range would need many lookups per element
  2. Hash map of complements: O(n)
  3. Brute force is required
  4. Binary search on the answer
Show the answer

A. Sort, then count pairs with sum ≤ 20 and subtract pairs with sum ≤ 9, each with an O(n) two-pointer pass; a hash map only answers exact sums, and a range would need many lookups per element — Range questions are order questions. Counting 'at most X' pairs with two pointers and subtracting is O(n log n) total.


6. Saying it out loud

"This is Two Sum's complement idea, but the question is approximate, closest rather than equal, so a hash map can't help; it only answers exact lookups. I'll sort and walk two pointers inward, recording the best gap: O(n log n) time, O(1) extra if I may sort in place. If the question were an exact difference, I'd go back to hashing with a Counter for the k = 0 case."


Check yourself

  1. When does a hash map solve a pair problem, and when doesn't it?
  2. Why is discarding the left value safe when the sum is below the target in the closest-sum walk?
  3. How does "largest sum below K" decide which pointer to move?
  4. Why do both pointers move right for the difference problem?
  5. What makes k = 0 special in the difference problem?
  6. How would you count pairs whose sum lies in a range?
Answers
  1. When the partner is an exact value (sum equals, difference equals). Not when the question is approximate or ordered (closest, below, within a range).
  2. Any other partner for that left value is smaller than the current right value, giving an even smaller sum, so its best possible pair has already been considered.
  3. If the sum fits (< K), record it and move left up (it's the best for that left value); otherwise move right down (that right value can't fit with anything remaining).
  4. In sorted order with i < j, advancing j grows the difference and advancing i shrinks it, so a fast/slow walk steers toward k.
  5. A value pairs with itself, so it needs at least two occurrences; counts, not a set, decide it.
  6. Count pairs with sum ≤ hi and subtract pairs with sum ≤ lo − 1, each with a sorted two-pointer pass.