Two Pointers: Find a Pair With a Target Sum in a Sorted Array
One problem, three stages: make it work, make it fast, make it lean. Step through each stage in the visualizer, then run all three on a big input in the benchmark and watch the brute force overheat.
The real-world version
A payments service keeps settled amounts sorted. Reconciliation needs to know whether two settlements add up exactly to a disputed total, across millions of rows, without loading a second copy into memory.
The problem
Given a sorted array of integers nums and an integer target, return the indices of two different elements that add up to target, or None if no pair exists.
nums = [1, 4, 6, 9, 13, 17, 22], target = 19 → (2, 4) # 6 + 13
Stage 1 · Smelt: Make it work
Check every pair. The outer loop fixes i, the inner loop tries every j after it. It's correct and it's the right first step: it proves you understand the question before you optimise.
def pair_sum(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 NoneWhy it's not enough: Doesn't scale: 1 million rows means about 500 billion pair checks.
Stage 2 · Hammer: Make it fast
For each value, the partner you need is target - value. Remember every value you've already passed in a hash map, and each lookup is O(1). One pass, no nested loop.
def pair_sum(nums, target):
seen = {} # value -> index
for i, x in enumerate(nums):
need = target - x
if need in seen:
return seen[need], i
seen[x] = i
return NoneWhy it's not enough: Fast, but it ignores that the array is sorted and costs a second copy of the data in memory.
Stage 3 · Polish: Make it lean
Start one pointer at each end. If the sum is too small, the left value can't pair with anything (the right one is already the largest left), so move L right. If it's too big, move R left. Every step discards one element for good.
def pair_sum(nums, target):
l, r = 0, len(nums) - 1
while l < r:
s = nums[l] + nums[r]
if s == target:
return l, r
if s < target:
l += 1 # nums[l] is too small for any partner
else:
r -= 1 # nums[r] is too big for any partner
return NoneWhy it holds up: Optimal: one pass and no extra memory. The sorted order is doing the work the hash map did.
X-ray: watch it run
Benchmark: will the forge overheat?
Run all three stages on a large input in your browser and compare the work each one does.
In the interview
Say out loud why moving a pointer is safe ("nums[l] can't pair with anything, because nums[r] is the largest value left"). Interviewers are listening for that proof, not just the code.
Go deeper: Two Pointer Technique · Two Sum with Hashing