Two Pointers

Concept

The Two Pointers technique is a heavily tested interview pattern used to optimize nested loops.
Whenever a problem asks you to search for pairs, reverse an array, or compare elements, a naive solution usually involves an $O(N^2)$ double for loop.

By placing two separate variables (pointers) at different locations in the array (usually one at the start, one at the end) and moving them toward each other, you can solve the problem in a single $O(N)$ pass.

Crucial Prerequisite: For the Two Pointers technique to work for searching/pairing, the array must usually be sorted.

Mental Model (Two Sum on a Sorted Array)

Find two numbers that add up to Target: 10.
Array: [1, 2, 3, 4, 6, 8, 9]

1. Put Left pointer on 1. Put Right pointer on 9. Sum = 10. (Found it instantly!)
2. What if Target was 8? 1 + 9 = 10. 10 is too big. Because the array is sorted, we know moving the Left pointer up will only make the sum bigger. We must move the Right pointer down to decrease the sum.
3. Move Right to 8. Sum = 1 + 8 = 9. Still too big.
4. Move Right to 6. Sum = 1 + 6 = 7. Too small! Now we must move the Left pointer up to increase the sum.
5. Move Left to 2. Sum = 2 + 6 = 8. Found it!

Implementation

Problem: Reverse an array in-place.

// Time Complexity: O(N)
// Space Complexity: O(1)
function reverseArray(arr: number[]): void {
    let left = 0;
    let right = arr.length - 1;

    // Loop until the pointers crash into each other
    while (left < right) {
        // Swap the elements
        let temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;

        // Squeeze inward
        left++;
        right--;
    }
}

Problem: Valid Palindrome (e.g., “racecar”)

function isPalindrome(s: string): boolean {
    let left = 0;
    let right = s.length - 1;

    while (left < right) {
        if (s[left] !== s[right]) return false;
        left++;
        right--;
    }
    return true;
}

Variations

1. Opposite Ends (Meet in the Middle): The standard pattern described above. One pointer starts at 0, the other at length - 1. Used for reversing, palindromes, and sorted pairs (Two Sum II).
2. Same Direction (Fast & Slow): Both pointers start at 0. One pointer moves faster than the other. Used for removing duplicates from a sorted array, or Linked List cycle detection.
3. Two Arrays: Pointer i starts at the beginning of Array1, Pointer j starts at the beginning of Array2. Used for merging two sorted arrays together (the core logic of Merge Sort).

Interview Questions

Q: The classic “Two Sum” problem asks you to find two numbers that add up to a target. Can you use the Two Pointers technique if the array is unsorted?
A: Technically, yes, but you have to sort the array first ($O(N \log N)$ time). If the interviewer asks for the absolute fastest time complexity, sorting the array is too slow.
For an unsorted Two Sum, you should abandon Two Pointers and use a Hash Map instead. The Hash Map stores the numbers you’ve seen so far, allowing you to find the pair in $O(N)$ time and $O(N)$ space.
However, if the interviewer says “You must use $O(1)$ space”, then sorting + Two Pointers is the mathematically optimal solution.

Q: A problem asks you to “Remove all instances of the number 0 from an array in-place”. How does Two Pointers solve this?
A: You use the Fast & Slow variation. Both pointers start at 0.
The Fast pointer is the explorer: it moves forward every single loop.
The Slow pointer is the builder: it only moves forward when it finds a valid number.
When the Fast pointer sees a non-zero, you write that value into the Slow pointer’s slot, and increment the Slow pointer. At the end of the loop, everything before the Slow pointer is completely clean of zeros.