Sorted Pair Search

Foundations

In the first lesson, two pointers walked inward from the ends of an array, settling positions as they met. Now, what if you need two values that add up to a goal, and each miss should tell you which pointer to move?

Sorting makes a miss informative. In sorted order, nums[left] is the smallest value still in play and nums[right] the largest. If nums[left] + nums[right] is below the goal, even the largest partner cannot lift nums[left] high enough, so left moves right. If the sum is above the goal, even the smallest partner leaves nums[right] too high, so right moves left. Either way, one value leaves for good.

Sort nums = [7, 1, 5, 3, 6] into [1, 3, 5, 6, 7] and look for two values summing to 11. 1 + 7 = 8 is too small, so left moves; 3 + 7 = 10, still too small; 5 + 7 = 12 is too big, so right moves; 5 + 6 = 11. Four checks replace all 10 pairs. Larger combinations reuse it: fix one value as an anchor, then pair-search the values after it.

• Sorting

  This lesson sorts first. Sorting is taught in the Search course; here you only need its cost, O(n log n).

  Open lesson

Case Scenario

3Sum asks for every distinct triple in nums whose values sum to 0. Fixing nums[i] as the anchor turns that into a pair search for -nums[i] among the values after it. In nums = [-1, 0, 1, 2, -1, -4], sorted to [-4, -1, -1, 0, 1, 2], the answer is [[-1, -1, 2], [-1, 0, 1]]: each triple once, even though -1 appears twice.

The direct approach tries every triple of indexes i < j < k: n(n - 1)(n - 2)/6 checks, 20 for these six values and about 166 million for 1,000. It also finds [-1, 0, 1] twice, once with each -1, so every hit must be sorted and stored in a set to drop repeats. Sorting the array once removes both costs: it gives each pair search a direction, and it puts equal values side by side, where they are easy to skip.