Two Pointers for Pair-Sum Problems

Welcome back! In our previous lessons, we've focused on pointer techniques where both pointers move in the same direction, like the sliding window pattern for finding minimum or maximum subarrays. Today, we shift gears to a different but equally powerful variation of the two-pointer technique.

This lesson introduces the opposite-end two-pointer pattern. Here, we initialize pointers at the two extremes of an array and move them toward each other. You'll learn how this approach elegantly solves "pair-sum" problems on sorted arrays, leveraging the sorted property to achieve linear time complexity with constant space. Mastering this is crucial, as it's a fundamental pattern in algorithm design and a building block for more complex problems like 3-Sum, which we'll tackle next.

The Problem: Two Sum on a Sorted Array

Let's consider a classic problem, often called "Two Sum II" (as seen in LeetCode 167):

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Return the indices of the two numbers as a pair.

For example, given numbers = [2, 7, 11, 15] and target = 9, the answer would be [1, 2] because numbers[0] + numbers[1] = 2 + 7 = 9.

You've likely solved the general "Two Sum" problem before, perhaps using a hash map. That approach works in O(n) time but requires O(n) space to store seen elements. The key constraint here is that the array is sorted. This property allows for a more space-efficient solution.

A brute-force approach would use nested loops to check every possible pair, resulting in an O(n²) time complexity. We can do much better.

The Two-Pointer Intuition: Converging for the Target

The core idea is to start with one pointer at the beginning of the array (left) and another at the very end (right). This pair (numbers[left], numbers[right]) represents the smallest and largest values in the array. We can then use their sum to intelligently narrow down the search space.

The following NeetCode video provides an excellent walkthrough of this logic. It first reviews the inefficient brute-force method and then clearly demonstrates the intuition behind the two-pointer optimization.

Let's break down the logic you just saw. At any given step, we have pointers left and right and we calculate current_sum = numbers[left] + numbers[right]. There are three possibilities:

1. current_sum == target: We've found our pair! The search is over.
2. current_sum > target: The sum is too high. To decrease it, we must use a smaller number. Since the array is sorted, moving the left pointer to the right would only increase the sum. Our only option is to move the right pointer to the left (right--), effectively trying a smaller value from the right side.
3. current_sum < target: The sum is too low. To increase it, we must use a larger number. Moving the right pointer to the left would only decrease the sum further. Therefore, we must move the left pointer to the right (left++) to try a larger value from the left side.

This simple logic allows us to discard one element at each step, either from the beginning or the end of our search window. Because the pointers only move towards each other, we will traverse the array at most once, leading to an O(n) time complexity.

This process of homing in on the target is why this is often called the converging pointers pattern.

A Complete Walkthrough

The "Hello Interview" article provides a clear textual explanation and visualization of this process. It reinforces the core idea of how this technique systematically eliminates pairs from consideration.

The image below shows a complete run of the algorithm. Follow the pointers start and end as they converge, and observe how the sum gets closer to the target of 40 until the correct pair (8, 32) is found.

Pattern Recognition and Implementation

Recognizing when to use this pattern is key. As the Dev Weekends resource highlights, a prompt involving a sorted array where you need to find pairs or triplets with a certain property is a strong signal for the two-pointer technique.

The primary advantage of this approach over a hash map is its O(1) space complexity, as no auxiliary data structure is needed. This trade-off is possible only because the array is sorted. If the original array were unsorted, you would have two choices:

1. Hash Map: O(n) time, O(n) space. Preserves original indices.
2. Sort + Two Pointers: O(n log n) time for sorting + O(n) for the two-pointer scan, for a total of O(n log n) time. The space complexity is O(1) or O(n) depending on the sorting algorithm's implementation. This approach loses the original indices.

For the "Two Sum II" problem, since the array is already sorted and we need indices from this sorted array, the two-pointer approach is optimal.

Conclusion

In this lesson, we explored the opposite-end two-pointer pattern. By initializing pointers at both ends of a sorted array and moving them inward based on their sum relative to a target, we can efficiently find a target pair in linear time and constant space.

Key Takeaways:

• The opposite-end two-pointer pattern is highly effective for search problems on sorted arrays.
• The core logic involves comparing the sum of the values at the two pointers with a target value.
• If the sum is too large, move the right pointer left.
• If the sum is too small, move the left pointer right.
• This approach reduces the search space at each step, achieving O(n) time complexity and O(1) space complexity.

This pattern is a fundamental tool in your algorithmic toolkit. In our next lesson, we will see how to apply it as a subroutine to solve the 3-Sum problem, where we'll search for triplets that sum to a target value.