Two-Pointer Technique for Array Problems

The Two-Pointer Technique: An Overview

At its core, the two-pointer technique involves using two integer indices (the "pointers") to iterate through an array in a controlled and intelligent way. Instead of using a single pointer that moves from start to end, or nested loops that result in quadratic time complexity, this approach often allows us to solve problems in a single pass, achieving linear time complexity.

There are several variations of this technique, but two are particularly common:

1. Opposite Directions: One pointer starts at the beginning of the array, and the other starts at the end. They move towards each other until they meet or cross. This is especially useful for problems involving sorted arrays where you need to find a pair of elements that satisfy a certain condition.
2. Same Direction (Fast/Slow): Both pointers start at or near the beginning of the array. One pointer (the "fast" one) explores the array, while the other (the "slow" one) marks a position or builds up the result. This pattern is excellent for problems that involve partitioning an array or handling elements based on a certain property, like removing duplicates or moving elements.

The image below provides a great visual summary of these two primary patterns.

Let's see these patterns in action with two classic problems.

Application 1: The "Two Sum" Problem

This is one of the most famous coding interview questions. We'll explore it using your preferred method: progressing from a simple but inefficient solution to the optimal one.

Problem: Given an array of integers and a target value, determine if there exists a pair of numbers in the array that sum up to the target.

We'll use the "takeUforward" tutorial as our guide, which walks through this exact progression.

Let's break down these approaches.

Approach 1: Brute-Force (O(n²))

The most straightforward way is to check every possible pair of numbers. You use a nested loop: the outer loop picks the first number, and the inner loop iterates through the rest of the array to see if any other number complements it to reach the target sum. As the article explains, this leads to a time complexity of $O(n^2)$, which is too slow for large inputs in an interview setting.

Approach 2: Using a HashMap (O(n) Time, O(n) Space)

A significant improvement comes from using a HashMap. As you iterate through the array, for each element x, you calculate the required complement, y = target - x. Instead of searching the rest of the array for y (an $O(n)$ operation), you can check for its existence in a HashMap (an $O(1)$ average time operation). If y is not in the map, you add the current element x to the map and continue.

This brings the total time complexity down to $O(n)$. However, it requires $O(n)$ extra space for the HashMap. For the general, unsorted version of "Two Sum," this is the optimal solution. But what if the array is sorted, or we are allowed to sort it? Can we do better in terms of space?

Approach 3: Two Pointers (O(n) Time, O(1) Space)

This is where the opposite-direction two-pointer pattern shines. This approach is optimal when the array is sorted.

1. Sort the array if it isn't already. This takes $O(n\log n)$ time.
2. Initialize two pointers: left = 0 and right = n - 1.
3. Loop as long as left < right:
   • Calculate currentSum = array[left] + array[right].
   • If currentSum == target, you've found your pair.
   • If currentSum < target, you need a larger sum. Since the array is sorted, you can achieve this by moving the left pointer one step to the right (left++).
   • If currentSum > target, you need a smaller sum. You achieve this by moving the right pointer one step to the left (right--).

This process systematically eliminates possibilities in linear time after the initial sort. The total time complexity is dominated by the sort, making it $O(n\log n)$. If the array is already sorted, the search itself is just $O(n)$. Most importantly, it uses $O(1)$ extra space, making it more space-efficient than the HashMap approach.

The following image visualizes this exact process.

For a dynamic explanation, the video from "take U forward" is excellent.

Application 2: Move Zeros to End

Now let's look at a problem that uses the same-direction (fast/slow) pointer pattern.

Problem: Given an array of integers, move all the 0's to the end of it while maintaining the relative order of the non-zero elements. This must be done in-place without making a copy of the array.

Example: [1, 0, 2, 0, 3] -> [1, 2, 3, 0, 0]

Approach 1: Brute-Force (O(n) Time, O(n) Space)

A simple solution is to create a new temporary array. You iterate through the original array and copy all non-zero elements into the temporary array. Then, you copy the elements from the temporary array back into the beginning of the original array. Finally, you fill the remaining spots in the original array with zeros. This works, but it violates the "in-place" constraint by using $O(n)$ extra space.

Approach 2: Two Pointers (O(n) Time, O(1) Space)

We can solve this optimally in-place using two pointers moving in the same direction.

1. Initialize a "slow" pointer, let's call it j, to 0. This pointer will keep track of the next position where a non-zero element should be placed.
2. Initialize a "fast" pointer, i, to 0. This pointer will iterate through the entire array to find non-zero elements.
3. Iterate with the fast pointer i from 0 to n-1:
   • If array[i] is not zero, it means we've found a non-zero element that needs to be moved to the j-th position.
   • We perform a swap: swap(array[i], array[j]).
   • After the swap, we increment j to point to the next position for a non-zero element.

After the loop finishes, all non-zero elements will be at the beginning of the array (from index 0 to j-1), and all zeros will have been swapped to the positions from j to the end. Crucially, the relative order of the non-zero elements is preserved.

Let's watch a video that demonstrates this partitioning logic.

And here's the corresponding text-based resource for reference.

Java Implementation

Here is a summary of the optimal Java code for both problems.

Two Sum (on a sorted array)

public class TwoSum {
    public static int[] twoSum(int[] arr, int target) {
        Arrays.sort(arr); // O(n log n), skip if already sorted
        int left = 0;
        int right = arr.length - 1;

        while (left < right) {
            int sum = arr[left] + arr[right];
            if (sum == target) {
                // In a real problem, you might need to return original indices.
                // For this example, we just confirm existence or return values.
                return new int[]{arr[left], arr[right]};
            } else if (sum < target) {
                left++;
            } else { // sum > target
                right--;
            }
        }
        return new int[]{-1, -1}; // No pair found
    }
}

Move Zeros to End

public class MoveZeros {
    public static void moveZeroes(int[] nums) {
        int j = 0; // "slow" pointer for the next non-zero position
        for (int i = 0; i < nums.length; i++) { // "fast" pointer
            if (nums[i] != 0) {
                // Swap the non-zero element with the element at j
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
                j++;
            }
        }
    }
}

Conclusion

Today, you've added a fundamental algorithmic pattern to your toolkit. The two-pointer technique is a prime example of how a clever approach can dramatically improve an algorithm's efficiency, often reducing time complexity from $O(n^2)$ to $O(n)$ and space complexity from $O(n)$ to $O(1)$.

Key Takeaways:

• Two-Pointer Technique: An efficient pattern for array problems that avoids nested loops by using two indices to traverse the array.
• Opposite Directions: Ideal for sorted arrays to find pairs satisfying a condition (e.g., Two Sum). Pointers start at both ends and move inwards.
• Same Direction (Fast/Slow): Excellent for partitioning an array in-place (e.g., Move Zeros). A slow pointer marks a boundary while a fast pointer scans the array.
• Efficiency: The primary goal is to achieve linear time $O(n)$ and constant space $O(1)$ complexity.

In our next lesson, we will explore another essential array algorithm: Kadane's algorithm. You will learn how to apply this dynamic programming-based technique to solve the "Maximum Subarray Sum" problem in a single, elegant pass.