Two-Pointer Technique for Sorted Arrays

1. The Core Idea: From Brute Force to Efficiency

Imagine you're given a sorted array and asked to find two numbers that meet a certain condition—for example, summing up to a target value. The most straightforward approach is to use nested loops: pick the first number, then loop through all the other numbers to see if you can form a pair that works. Then, pick the second number and repeat. This is the brute-force method.

With an array of size $n$, this approach takes roughly $n\times n$ operations, leading to a time complexity of $O(n^2)$. For large arrays, this is too slow. The two-pointer technique offers a brilliant optimization that reduces the time complexity to just $O(n)$.

The idea is simple: instead of iterating with two nested loops, we use two pointers (which are just integer indices) and move them intelligently through the array in a single pass.

There are a few variations of this pattern. We'll start with the most common one for sorted arrays, where one pointer starts at the beginning of the array and the other starts at the end.

2. The Classic Problem: "Two Sum" on a Sorted Array

Let's ground this in a concrete, famous interview problem: Given a sorted array of integers, find two numbers that add up to a specific target.

Problem:

• Input: numbers = [2, 7, 11, 15], target = 9
• Output: The indices of the two numbers, e.g., [0, 1] (because numbers[0] + numbers[1] == 9).

The Two-Pointer Algorithm:

1. Initialize Pointers: Create a left pointer at index 0 and a right pointer at the last index (numbers.length - 1).
2. Loop and Check: While left is less than right:
   a. Calculate the sum of the values at the pointers: sum = numbers[left] + numbers[right].
   b. Compare the sum to the target:
   * If sum == target, you've found your pair! Return the indices.
   * If sum < target, the sum is too small. To increase it, you must move the left pointer one step to the right (left++), as the array is sorted and all values to the right are larger.
   * If sum > target, the sum is too large. To decrease it, you must move the right pointer one step to the left (right--), as all values to the left are smaller.
3. End Condition: If the loop finishes (i.e., left crosses right) and no pair has been found, it means no such pair exists.

This logic works because the sorted nature of the array gives us a critical piece of information with every step. We always know which way to move a pointer to get closer to our target sum.

The following article walks through this exact problem, showing the brute-force method first and then the optimized two-pointer solution.

This next video provides a fantastic visual walkthrough, comparing the brute-force, a binary search approach, and finally the optimal two-pointer solution.

3. A Different Flavor: Merging Two Sorted Arrays

The two-pointer technique isn't limited to pointers moving from opposite ends. Another common variant involves pointers moving in the same direction across one or more arrays. A great example is merging two sorted arrays into a single sorted array.

Problem:

• Input: array1 = [10, 15, 22, 80], array2 = [5, 8, 11, 70, 90]
• Output: [5, 8, 10, 11, 15, 22, 70, 80, 90]

The Algorithm:

1. Initialize: Create a pointer for each input array, p1 for array1 and p2 for array2, both starting at index 0. Create a new result array large enough to hold all elements.
2. Compare and Copy: While both p1 and p2 are within the bounds of their respective arrays:
   a. Compare array1[p1] and array2[p2].
   b. Copy the smaller of the two elements into the result array.
   c. Increment the pointer of the array from which you just copied the element.
3. Copy Remainder: Once one of the loops finishes, one of the arrays will still have elements left. Copy all remaining elements from that array to the end of the result array.

This video demonstrates the merging process along with other applications of the two-pointer pattern.

Here's a sample Java implementation for merging two sorted arrays:

public int[] mergeSortedArrays(int[] arr1, int[] arr2) {
    int n1 = arr1.length;
    int n2 = arr2.length;
    int[] result = new int[n1 + n2];

    int p1 = 0; // Pointer for arr1
    int p2 = 0; // Pointer for arr2
    int pResult = 0; // Pointer for result array

    // Compare elements and fill the result array
    while (p1 < n1 && p2 < n2) {
        if (arr1[p1] <= arr2[p2]) {
            result[pResult++] = arr1[p1++];
        } else {
            result[pResult++] = arr2[p2++];
        }
    }

    // Copy remaining elements from arr1, if any
    while (p1 < n1) {
        result[pResult++] = arr1[p1++];
    }

    // Copy remaining elements from arr2, if any
    while (p2 < n2) {
        result[pResult++] = arr2[p2++];
    }

    return result;
}

4. How to Spot the Pattern

As you prepare for interviews, the key is not just to know the pattern, but to recognize when to use it. Here are some clues in a problem description that should make you think "two-pointers":

• "Sorted array" or "sorted sequence": This is the biggest hint. The sorted property is what allows you to make intelligent decisions about moving the pointers.
• Finding pairs or triplets with a certain property: Problems like "Two Sum," "Three Sum," or finding a pair that is closest to a target value are prime candidates.
• Comparing elements from opposite ends: Any problem that involves looking at the first and last elements simultaneously, like checking if a string is a palindrome.
• Needing an in-place modification: Problems like "Remove Duplicates from Sorted Array" or "Move Zeroes to End" can be solved efficiently by using a slow and a fast pointer to overwrite the array.

Conclusion

You've now learned one of the most versatile and efficient algorithmic patterns for interviews. The two-pointer technique transforms problems that seem to require quadratic time complexity into linear time solutions, a massive performance gain.

Here are the main takeaways:

• The two-pointer technique uses two indices to process an array in a single pass, achieving $O(n)$ time complexity.
• For sorted arrays, the "opposite ends" approach is perfect for finding pairs that sum to a target, by intelligently shrinking the search space.
• The "same direction" approach is effective for problems like merging two sorted arrays.
• The key to the technique is leveraging the array's sorted property to decide which pointer to move next.

In our next lesson, we will explore a related pattern: the sliding window technique. It also uses two pointers, but in a different way to solve a different class of problems, typically involving finding optimal subarrays within a larger array.