Two Pointers

Two pointers is a popular technique in the interview problems. As the name suggests, in this technique you have two pointers that are usually just variables pointing to the indices of the array. These pointers can move to, away, or in parallel with each other in a loop, depending on the problem and the invariant you are keeping. Let's see some examples.

Palindromes and converging pointers

Checking if the string is a palindrome is a great example of using two pointers that move to each other. In the following code, two pointers – named l and r (for left and right) – point to the characters we compare with each other:

boolean isPalindrome(String s) {
    if (s == null || s.length() == 0)
        return true;

    int l = 0, r = s.length() - 1;
    while (l < r) {
        if (s.charAt(l) != s.charAt(r))
            return false;
        l++; r--;
    }

    return true;
}

A similar approach can be applied to the following problem. Can you solve it?

Hint
Solution

Another good problem for this technique is the following one:

Hint
Solution

Sums

This technique often works with sorted arrays. Again, we have two pointers that move to each other, but the reasoning is different: when the number under the left pointer grows, the number under the right pointer has to decrease. It's best to illustrate this with the following problem. Can you solve it?

Hint
Solution

In-place array modification

Sometimes, you are asked to modify an array in-place – without creating any other arrays or data structures. In many such problems, you need to keep two pointers: one iterating through the array, and the second one pointing to some other interesting place in it – for the example the one that you write to.

Try to solve the following problem to better understand what this means:

Hint
Solution

The following one is another good problem on the similar technique:

Hint
Solution

More two pointer problems

In the following problem, you need to keep pointers at the two arrays at the same time. Can you solve it?

Hint
Solution

The next problem is a great example of two pointers "following each other":

Hint
Solution

More practice problems

Here are some more good two pointers problems you can practice on: