Converging Pointers

They started at opposite ends, but I knew they were destined to meet in the middle.

When an array is sorted, it changes the way we can do stuff with it. In the Value-to-Index Mapping chapter, we used a hash map to map values to their indices, but if the array is sorted, can you leverage the sorted property to find pairs without using extra space?

Problem: Two Sum II (Sorted Array): (LeetCode Link) : Given a sorted array of integers numbers, find two numbers such that they add up to a specific target number. 💡 HintIf you pick a number at the beginning and a number at the end, what does their sum tell you?💡 HintIf the sum is too small, which pointer should you move to get a larger value? If it's too large, which pointer should you move to get a smaller value?

We have already solved this before using $O(N)$ time complexity and $O(N)$ space complexity. A sorted array will let us reduce space complexity to $O(1)$. The optimal solution here is to use a "converging pointers" technique. This technique uses two pointers that start at opposite ends of a sorted array and move towards each other, narrowing the search space with each step.

How It Works

1. Initialize Two Pointers: Start one pointer at the beginning (left = 0) and the other at the end (right = n-1) of the array.
2. Iterate Until Pointers Meet: (while left < right):
   • Calculate a value or check a condition based on the elements at nums[left] and nums[right].
   • Based on the result, you can definitively move one of the pointers inward. Because the array is sorted, you know that moving the left pointer will always result in a larger value, and moving the right pointer will always result in a smaller one.
3. Terminate: The loop ends when the pointers meet or cross, or when a solution is found.

Walkthrough: Solving "Two Sum II"

Let's apply the pattern to our two sum problem.

1. Initialize two pointers: left = 0 and right = nums.length - 1.
2. Start a loop that continues as long as left < right.
3. Inside the loop, calculate the currentSum = nums[left] + nums[right].
4. The Decision Logic:
   • If currentSum == target, we've found our pair. We can return their indices.
   • If currentSum < target, our sum is too small. The only way to increase the sum is to move the left pointer to a larger value (left++). There's no point in moving right inwards, as that would only make the sum even smaller.
   • If currentSum > target, our sum is too large. The only way to decrease the sum is to move the right pointer to a smaller value (right--).
5. This process guarantees that we check all potential pairs efficiently in a single pass.

def two_sum_sorted(nums, target):
    left, right = 0, len(nums) - 1

    while left < right:
        current_sum = nums[left] + nums[right]

        if current_sum == target:
            return [left, right]
        elif current_sum < target:
            left += 1
        else:
            right -= 1

    return [-1, -1]

public int[] twoSumSorted(int[] nums, int target) {
    int left = 0, right = nums.length - 1;

    while (left < right) {
        int currentSum = nums[left] + nums[right];

        if (currentSum == target) {
            return new int[]{left, right};
        } else if (currentSum < target) {
            left++;
        } else {
            right--;
        }
    }

    return new int[]{-1, -1};
}

std::vector<int> twoSumSorted(std::vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;

    while (left < right) {
        int currentSum = nums[left] + nums[right];

        if (currentSum == target) {
            return {left, right};
        } else if (currentSum < target) {
            left++;
        } else {
            right--;
        }
    }

    return {-1, -1};
}

Complexity Analysis

Time Complexity: $O(N)$ In the worst case, the left and right pointers will each traverse the array only once.

Space Complexity: $O(1)$

More Problems & Variations

This technique of two pointers walking to each other can be applied to several other problems. Try these out:

1. 3Sum: Find all unique triplets in the array which give the sum of zero. 💡 HintSort the array, then iterate with a main pointer. For each element, use the converging two-pointer technique on the rest of the array to find pairs that sum to the required value.
2. Valid Palindrome 💡 HintCheck if a string is a palindrome by comparing characters from both ends and moving inwards.
3. Container With Most Water: Find two lines that together with the x-axis form a container, such that the container contains the most water. 💡 HintStart with pointers at the widest possible container. To have a chance at a larger area, which pointer should you move inward? The one pointing to the shorter line or the longer line?