Closest Pair from Two Arrays: Sort + Two Pointers in O(n log n)
Finding the pair with the smallest absolute difference — one element from each array — is a classic two-pointer problem that rewards clear thinking about sorted order. The brute-force approach checks all n×m pairs in O(n*m) time. With sorting, you can do it in O(n log n) with a single linear scan. This exact pattern — sort then two-pointer — appears throughout interview problems involving pairs, differences, and closest values.
Why Sorting Unlocks the Two-Pointer Approach
Once both arrays are sorted, you can make a guaranteed decision at each step: if first[i] < second[j], then first[i] paired with any element further right in second will only increase the difference. So advance i. This greedy move is only valid because the arrays are sorted — that's the key insight.
Algorithm Walkthrough
# first = [4, 1, 8] → sorted: [1, 4, 8]
# second = [12, 3, 17] → sorted: [3, 12, 17]
#
# i=0 j=0: |1-3|=2 → best so far: [1,3] → first[0]Code Implementation
def find_closest_pair(first, second):
first.sort()
second.sort()
i, j = 0, 0
min_diff = float('inf')
closest_pair = []
while i < len(first) and j < len(second):
diff = abs(first[i] - second[j])
if diff < min_diff:
min_diff = diff
closest_pair = [first[i], second[j]]
# Advance the pointer pointing to the smaller value
if first[i] < second[j]:
i += 1
else:
j += 1
return closest_pair
print(find_closest_pair([4, 1, 8], [12, 3, 17])) # [4, 3]
print(find_closest_pair([-1, -3, -5], [2, 4, 6])) # [-1, 2]
print(find_closest_pair([1], [1])) # [1, 1]
Complexity Analysis
- Time: O(n log n) — dominated by sorting; the two-pointer scan is O(n + m).
- Space: O(1) — only a handful of variables regardless of input size (sorting is in-place).
Edge Cases
assert find_closest_pair([4, 1, 8], [12, 3, 17]) == [4, 3]
assert find_closest_pair([1], [2]) == [1, 2] # single elements
assert find_closest_pair([-1, -3, -5], [2, 4, 6]) == [-1, 2] # negatives
assert find_closest_pair([1, 1, 1], [2, 2, 2]) == [1, 2] # duplicates
assert find_closest_pair([5], [5]) == [5, 5] # exact match (diff = 0)
print("All tests passed!")
Common Mistake: Forgetting to Sort First
If you apply the two-pointer logic to unsorted arrays, the "advance the smaller pointer" decision is meaningless — you'd miss the closest pair. Always sort before running the pointer scan.
Key Takeaways
- Sort both arrays, then use two pointers starting at the left of each.
- At each step, record the current pair if it's the closest so far, then advance the pointer with the smaller value.
- Time: O(n log n) from sorting; Space: O(1) extra.
- This sort + two-pointer pattern generalizes: use it whenever you need to efficiently find closest/matching pairs across two sorted collections.
What to Learn Next
This problem is a stepping stone to harder two-pointer problems. Try 3Sum (find all triplets summing to zero), which adds a third pointer and de-duplication logic. Then explore merge intervals and meeting rooms problems, which use the same "sort first, then scan" foundation. Finally, revisit binary search as an alternative to two pointers when one array is much larger than the other.
