Two Pointers Technique

The Two Pointers Technique

When working with arrays or linked lists, the most straightforward solution often involves nested loops. This usually results in a time complexity of $O(n^2)$ , which is fine for small datasets but becomes painfully slow as the input size grows. The two-pointers technique is a clever strategy to optimize these problems, often reducing the time complexity to a linear $O(n)$ while using constant space.

This pattern involves using two indices (or pointers) that traverse a data structure. They might move toward each other, away from each other, or in the same direction at different speeds. It's a fundamental tool for technical interviews because it demonstrates an ability to think beyond brute-force solutions and write efficient, memory-conscious code.

The Two-Pointers Technique is a simple yet powerful strategy where you use two indices (pointers) that traverse a data structure - such as an array, list, or string - either toward each other or in the same direction to solve problems more efficiently

Converging Pointers

The most common application of this pattern is in sorted arrays. By placing one pointer at the beginning and another at the end, you can process the data from both sides simultaneously, converging toward the middle.

Let's consider a classic problem: find if a pair of numbers in a sorted array sums up to a target value, X. The naive approach would be to use two nested loops, checking every possible pair. That works, but it's inefficient.

// Brute-force O(n^2) approach
boolean findPairSum(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[i] + arr[j] == target) {
                return true;
            }
        }
    }
    return false;
}

Now, let's use two pointers. We'll call them left and right. left starts at index 0, and right starts at the last index. We then check the sum of the values at these pointers.

If arr[left] + arr[right] equals the target, we've found our pair.
If the sum is less than the target, we need a larger value. Since the array is sorted, we increment left to move toward a bigger number.
If the sum is greater than the target, we need a smaller value. We decrement right to move toward a smaller number.

This process continues until the pointers meet or cross each other. Since each pointer traverses the array only once, the time complexity is $O(n)$ . This is a massive improvement over the $O(n^2)$ brute-force method, and we did it without using any extra memory.

Fast and Slow Pointers

Another powerful variant is the fast and slow pointer pattern, famously known as the . Here, two pointers start at the same position but move at different speeds. The 'slow' pointer moves one step at a time, while the 'fast' pointer moves two steps.

This technique is the go-to solution for detecting cycles in a linked list. If there is no cycle, the fast pointer will reach the end of the list first. However, if a cycle exists, the fast pointer will eventually enter the cycle and lap the slow pointer, and they will meet at some node within the cycle.

Let's see the logic in pseudocode:

def has_cycle(head):
    slow = head
    fast = head

    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next

        # If pointers meet, there is a cycle
        if slow == fast:
            return True
    
    # If fast pointer reaches the end, no cycle
    return False

In-Place Manipulation

The two-pointers technique shines when you need to modify a data structure , meaning without allocating a new one. This is a common constraint in coding interviews to test your understanding of memory management.

Reversing an Array To reverse an array in-place, use converging pointers. Start left at the beginning and right at the end. Swap the elements at left and right, then move left forward and right backward. Repeat until they meet.

function reverseInPlace(arr) {
    let left = 0;
    let right = arr.length - 1;

    while (left < right) {
        // Swap elements
        const temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;

        // Move pointers
        left++;
        right--;
    }
}

Removing Duplicates from a Sorted Array Another common task is to remove duplicates from a sorted array in-place. We can use two pointers moving in the same direction but at different speeds.

One pointer, let's call it write_ptr, will mark the end of the new, duplicate-free array. The other, read_ptr, will iterate through the entire array. If the element at read_ptr is different from the element at write_ptr, we copy the value from read_ptr to the position right after write_ptr and then advance write_ptr.

Mastering these patterns is less about memorising code and more about understanding the underlying logic. When you see a problem involving sorted arrays or searching for pairs or cycles, the two-pointers technique should be one of the first strategies that comes to mind.

Ready to test your understanding?

Quiz Questions 1/5

What is the primary advantage of using the two-pointers technique over a nested loop for problems like finding a pair that sums to a target in a sorted array?

Quiz Questions 2/5

When using two pointers (left at the start, right at the end) to find a pair in a sorted array that sums to a target X, what should you do if arr[left] + arr[right] is less than X?

By applying these techniques, you can write solutions that are not only correct but also highly efficient, a key differentiator in any software engineering role.

Mastering DSA for Coding Interviews