Two Pointers

Two pointers is an extremely common technique for solving problems related to arrays and strings. It is also used with other concepts like sliding window, prefix sum, and cycle detection.

Before getting started, the first question we need to answer is, Why learn this technique? Let's just think about how we might solve a problem without it.

Imagine you are given an array of integers as input and asked to find a pair of numbers that add up to a target. The first idea that comes to our mind is to use a nested for loop.

You would take the first number in the outer loop, then use that number and add it to every number in the inner loop one at a time, and check if the resulting sum is equal to the target. Then you'd take the second number, and loop through every number after it... and so on.

This "naive approach" works fine, but there is a clear issue with it. If your array has 10 elements, you end up doing roughly $10 \times 10 = 100$ checks. If your array has 1,000 elements, you're suddenly doing $1,000 \times 1,000 = 1,000,000$ checks! This is what we call $O(n^2)$ or "quadratic time." As your input array gets bigger, the amount of work grows much, much faster.

The strength of the two-pointer technique is that it avoids this. It's a clever way to check pairs without needing a nested loop. In many cases, it lets you solve the problem by passing over the array just once. This reduces the time complexity to $O(n)$ or "linear time." Now, if your array has 1,000 elements, you only do about 1,000 checks, not a million. That's a massive improvement and the key reason this pattern is super efficient.

To get started, two pointers involve having two integer variables, often named as i and j, or right and left. These variables represent the indices of the input.

The indices are then moved along the input; this movement depends on the problem we are trying to solve.

Here are the different variations of the same idea:

• Same direction – Pointers start at the same end and move in the same direction.
• Opposite direction – Pointers start at the opposite ends of the input and move towards each other. Let's start by understanding the first variation.

Let's convert this idea into instructions:

• Both pointers (i and j) start at index 0.
• One pointer (j) moves forward in every iteration.
• The other pointer (i) only moves when some condition is true.

Here's how the idea looks as pseudocode. The "fast" pointer j scans the whole array, so the loop runs as long as j is in the array.

function two_pointers_same(arr):
    i = 0  // This is the "slow" pointer
    j = 0  // This is the "fast" pointer
    while j < arr.length:
        // Do some logic based on the problem.
        // For example: if (arr[j] meets a condition):
        //     Do something (maybe swap arr[i] and arr[j])
        //     i++  // <-- Notice 'i' only moves inside the 'if'
        j++ // <-- Notice 'j' *always* moves

Opposite Direction

In basic terms:

• Declare two integer variable pointers, i and j, or right and left
• Start one pointer i at index 0 and the other pointer j at the last index, i.e, input.length - 1
• Move these two indices along the input. For each iteration, move the pointers towards each other until they meet. Incrementing and decrementing the pointers depends on the type of problem you are solving.

Here is the pseudo-code for the above idea:

function two_pointers(arr):
	i = 0
	j = arr.length - 1
	while i < j:
		// Do some logic based on the problem
		i ++
		j --