The Two Pointer Technique

The two pointer technique is a near necessity in any software developer's toolkit, especially when it comes to technical interviews. In this guide, we'll cover the basics so that you know when and how to use this technique.

What is the pattern?

The name two pointers does justice in this case, as it is exactly as it sounds. It's the use of two different pointers (usually to keep track of array or string indices) to solve a problem involving said indices with the benefit of saving time and space. See the below for the two pointers highlighted in yellow.

But what are pointers? In computer science, a pointer is a reference to an object. In many programming languages, that object stores a memory address of another value located in computer memory, or in some cases, that of memory-mapped computer hardware.

When do we use it?

In many problems involving collections such as arrays or lists, we have to analyze each element of the collection compared to its other elements.

There are many approaches to solving problems like these. For example we usually start from the first index and iterate through the data structure one or more times depending on how we implement our code.

Sometimes we may even have to create an additional data structure depending on the problem's requirements. This approach might give us the correct result, but it likely won't give us the most space and time efficient result.

This is why the two-pointer technique is efficient. We are able to process two elements per loop instead of just one. Common patterns in the two-pointer approach entail:

1. Two pointers, each starting from the beginning and the end until they both meet.
2. One pointer moving at a slow pace, while the other pointer moves at twice the speed.

These patterns can be used for string or array questions. They can also be streamlined and made more efficient by iterating through two parts of an object simultaneously. You can see this in the Two Sum problem or Reverse a String problems.

Running through an example

One usage is while searching for pairs in an array. Let us consider a practical example: assume that you have a sorted array arr.

You're tasked with figuring out the pair of elements where arr[p] + arr[q] add up to a certain number. (To try this problem out, check the Two Sum and Sorted Two Sum problems here.)

The brute force solution is to compare each element with every other number, but that's a time complexity of O(n^2). We can do better!

So let's optimize. You need to identify the indices pointer_one and pointer_two whose values sum to the integer target.

Let's initialize two variables, pointer_one and pointer_two, and consider them as our two pointers.

1int pointerOne = 0;
2int pointerTwo = arr.length - 1;

These snippets declare two pointers, typically used to traverse an array or a similar data structure. In C++, the calculation of pointerTwo assumes that arr is a statically defined array. If it were a dynamic array or a standard container like std::vector, you would use arr.size() instead.

Note that len(arr)-1 helps to get the last index possible in an array.

Also observe that when we start, pointer_one points to the first element of the array, and pointer_two points to the last element.

This won't always be the case with this technique (we'll explore the sliding window concept later, which uses two pointers but have them move in a different direction). For our current purposes, it is more efficient to start wide, and iteratively narrow in (particularly if the array is sorted).

1private static int[] twoSum(int[] arr, int target) {
2    Arrays.sort(arr); // Sorting is optional, based on the specific logic
3    int left = 0;
4    int right = arr.length - 1;
5    while(left < right) {
6        // logic to find the two numbers that add up to target
7    }
8}

Since the array is already sorted, and we're looking to process an index at each iteration, we can use two pointers to process them faster. One pointer starts from the beginning of the array, and the other pointer begins from the end of the array, and then we add the values at these pointers.

Once we're set up, what we want to do is check if the current pointers already sum up to our target. This might happen if the correct ones are on the exact opposite ends of the array.

Here's what the check might look like:

1if (arr[left] + arr[right] == target) {
2    return new int[] {arr[left], arr[right]};
3}

These snippets implement the logic to check if the sum of two numbers from an array equals the target value, returning the appropriate result. In Python, the code snippet returns a boolean value, while the other languages return the indices or values of the two numbers that add up to the target.

However, it likely will not be the target immediately. Thus, we apply this logic: if the sum of the values is less than the target value, we increment the left pointer (move your left pointer pointer_one one index rightwards).

And if the sum is higher than the target value, we decrement the right pointer (correct the position of your pointer pointer_two if necessary).

1} else if (arr[left] + arr[right] < target) {
2    left++;
3} else {
4    right--;
5}

It's crucial to see that how both indices were moving in conjunction, and how they depend on each other.

We kept moving the pointers until we got the sum that matches the target value-- or until we reached the middle of the array, and no combinations were found.

The time complexity of this solution is O(n) and space complexity is O(1), a significant improvement over our first implementation!

Another Example

In addition, to the previous example, the two pointer technique can also involve the pattern of using a fast pointer and a slow pointer.

1Node fast = head, slow = head

The idea is to move the fast pointer twice as quickly as the slow pointer so the distance between them increases by 1 at each step.

1while (fast!=null && fast.next!=null) {
2  slow = slow.next;
3  fast = fast.next.next;

One Pager Cheat Sheet

• The Two Pointer Technique is an essential tool for software developers to use, especially when faced with technical interviews.
• Pointers are references to objects, and the two pointers technique is used to track and compare array or string indices to save time and space.
• The two-pointer technique is an efficient approach to processing two elements of a data structure, such as an array or list, per loop in order to solve problems involving collections.
• The two-pointer technique is a search algorithm used to solve problems involving collections such as arrays and lists by comparing elements pointed by two pointers and updating them accordingly.
• By initializing two variables pointer_one and pointer_two and evaluating their values with respect to the given target, we can find pairs in an array that sum up to a certain number with a O(n) time complexity.
• Two pointers are used in different programming languages to start from the ends of an array and iteratively narrow in to find thetarget` more efficiently than other techniques.
• We can use two pointers starting from the beginning and end of an already sorted array to check if they 'sum up' to the target, which is done by a simple comparison statement if sum == target.
• The logic applied is to increment the left pointer if the sum of values is less than the target value and decrement the right pointer if it is higher than the target value.
• Understand that if arr[pointer_one] < target-arr[pointer_two], pointer_one should be moved forward to get closer to the desired magnitude.
• The process of using a fast pointer and a slow pointer is another way to apply the two pointer technique, which can have O(n) time complexity and O(1) space complexity.
• Using Slow and Fast Pointers can detect cycles in a linked list, such as when a node points back to a previous node.
• By setting fast to traverse twice as quickly as slow, the distance between them increases at each step.
• If both pointers reach the same node, then there is a cycle present in the linked list.
• The code attached provides an O(n) or linear time complexity.
• Yes, the two pointer technique can reduce both time and space complexity down to O(n), thus improving overall performance.
• Two-pointers are useful for iterating over and combining two sorted arrays.
• The two-pointer technique involves placing two pointers at opposite ends of an array and comparing their values to reverse its order by swapping or shifting items.