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:
- Closest sum: the pair whose sum is closest to a target (no exact match required).
- Largest sum below a limit: the biggest pair sum that stays strictly under K.
- 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
"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.
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
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.
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.
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.
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).
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.
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.)
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?
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?
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
- When does a hash map solve a pair problem, and when doesn't it?
- Why is discarding the left value safe when the sum is below the target in the closest-sum walk?
- How does "largest sum below K" decide which pointer to move?
- Why do both pointers move right for the difference problem?
- What makes k = 0 special in the difference problem?
- How would you count pairs whose sum lies in a range?
Answers
- When the partner is an exact value (sum equals, difference equals). Not when the question is approximate or ordered (closest, below, within a range).
- 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.
- 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).
- In sorted order with i < j, advancing j grows the difference and advancing i shrinks it, so a fast/slow walk steers toward k.
- A value pairs with itself, so it needs at least two occurrences; counts, not a set, decide it.
- Count pairs with sum ≤ hi and subtract pairs with sum ≤ lo − 1, each with a sorted two-pointer pass.