Two-Pointer Technique for Sorted Arrays

The Two-Pointer Technique: An Overview

At its core, the "two-pointer" technique is exactly what it sounds like: you use two integer indices (the "pointers") to traverse a data structure, usually an array. By moving these pointers according to some logic, you can efficiently process pairs or subarrays.

There are a few common patterns. For this lesson, we will focus on the most common one used with sorted arrays: pointers at opposite ends moving towards each other.

This technique shines when a problem involves finding pairs of elements in a sorted array that satisfy a certain condition. Let's dive into the classic problem that demonstrates this perfectly.

The "Two Sum" Problem on a Sorted Array

Imagine you're given a sorted array of integers and a target number. Your task is to find out if there's a pair of numbers in the array that adds up exactly to that target.

Problem: Given arr = [2, 7, 11, 15] and target = 9, find the pair.
Solution: The pair is (2, 7).

How would you solve this?

• Brute-Force Approach: The most straightforward way is to use nested loops. The outer loop picks an element, and the inner loop checks every other element to see if their sum matches the target. This works, but with two nested loops, its time complexity is $O(n^2)$, which is too slow for large inputs in competitive programming.

• A Better, but Not Optimal, Approach: Since the array is sorted, you could iterate through each element x and use binary search to look for target - x in the rest of the array. This would be an $O(n\log n)$ solution, which is much better, but we can still do better!

• The Two-Pointer Approach ($O(n)$): This is where the magic happens. By using two pointers, we can solve this in a single pass.

To see a great visual explanation and a live coding demonstration of this approach, please watch the following video.

The Logic Explained

As the video demonstrates, the logic is elegant and relies entirely on the array being sorted.

1. Initialize Pointers: Create a left pointer at the start of the array (index 0) and a right pointer at the end (index n-1).
2. Loop and Check Sum: Loop as long as left < right:
   • Calculate current_sum = arr[left] + arr[right].
   • If current_sum == target: You've found your pair! You can stop.
   • If current_sum < target: You need a larger sum. Since the array is sorted, the only way to increase the sum is to move the left pointer to the right (left += 1).
   • If current_sum > target: You need a smaller sum. The only way to decrease the sum is to move the right pointer to the left (right -= 1).

This process systematically eliminates pairs from consideration, ensuring you check all valid possibilities in a single pass.

Python Implementation

Here is a clean Python implementation based on the logic we just discussed.

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

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

        if current_sum == target:
            # Found the pair, return their indices or values
            print(f"Pair found: ({arr[left]}, {arr[right]})")
            return True
        elif current_sum < target:
            # The sum is too small, need a larger number.
            # Move the left pointer to the right.
            left += 1
        else: # current_sum > target
            # The sum is too large, need a smaller number.
            # Move the right pointer to the left.
            right -= 1

    # If the loop finishes, no pair was found
    print("No pair found.")
    return False

# Example
my_array = [-3, 1, 4, 6, 10, 45]
my_target = 16
two_sum_sorted(my_array, my_target) # Output: Pair found: (6, 10)

Another Example: Squares of a Sorted Array

Let's look at another problem where this pattern is useful, but in a slightly different way.

Problem: Given an array of integers nums sorted in non-decreasing order (e.g., [-4, -1, 0, 3, 10]), return an array of the squares of each number, also sorted in non-decreasing order.

A simple O(n \log n) solution is to square every number and then sort the resulting array. But can we do it in O(n) time? Yes, with two pointers!

The key insight is that the largest squared values will come from the numbers with the largest absolute values, which are at the extremes of the sorted input array.

The following video explains this clever approach.

The logic is as follows:

1. Initialize left = 0, right = n-1.
2. Create a result array of the same size, filled with placeholders.
3. Use a third pointer, write_pos, starting from the end of the result array (n-1).
4. In a loop, compare abs(arr[left]) and abs(arr[right]).
   • If abs(arr[left]) is smaller, the square of arr[right] is larger. Place it at result[write_pos] and decrement right.
   • Otherwise, the square of arr[left] is larger or equal. Place it at result[write_pos] and increment left.
5. Decrement write_pos in each iteration. Continue until the result array is filled.

This method builds the sorted array of squares from largest to smallest, all in one pass.

Conclusion

You've just learned one of the most common and effective patterns in competitive programming. The opposite-ends two-pointer technique is your go-to strategy when you encounter problems that involve finding pairs or processing elements from both ends of a sorted array.

Key Takeaways:

• The two-pointer technique is used to efficiently process arrays in linear time, $O(n)$.
• For sorted arrays, the "opposite-ends" pattern is extremely powerful.
• The core logic involves initializing pointers at the start and end and moving them inward based on a condition related to the problem (e.g., sum vs. target).
• This approach works by intelligently eliminating portions of the search space at each step, thanks to the sorted nature of the data.

Up Next:
The pattern we learned today is just one variant of the two-pointer technique. In the next lesson, we will explore another common pattern: the fast and slow pointers. You'll learn how it differs from the opposite-ends approach and what kinds of problems it is best suited to solve.