1. Overview
In this tutorial, we’ll discuss the two-pointer approach for solving problems involving arrays and lists. This technique is an easy and efficient way to improve the performance of our algorithm.
2. Technique Description
In many problems involving arrays or lists, we have to analyze each element of the array compared to its other elements.
To solve problems like these we usually start from the first index and loop through the array one or more times depending on our implementation. Sometimes, we also have to create a temporary array depending on our problem’s requirements.
The above approach might give us the correct result, but it likely won’t give us the most space- and time-efficient solution.
As a result, it is often good to consider whether our problem can be solved efficiently by using the two-pointers approach.
In the two-pointer approach, pointers refer to an array’s indexes. By using pointers, we can process two elements per loop, instead of just one.
Common patterns in the two-pointer approach involve:
- Two pointers each starting from the beginning and the end until they both meet
- One pointer moves at a slow pace while the other pointer moves at a faster pace
Both of the above patterns can help us to reduce the time and space complexity of our problems as we get the expected result in fewer iterations and without using too much additional space.
Now, let’s take a look at a few examples that will help us to understand this technique a bit better.
3. Sum Exists in an Array
Problem: Given a sorted array of integers, we need to see if there are two numbers in it such that their sum is equal to a specific value.
For example, if our input array is [1, 1, 2, 3, 4, 6, 8, 9] and the target value is 11, then our method should return true. However, if the target value is 20, it should return false.
Let’s first see a naive solution:
public boolean twoSumSlow(int[] input, int targetValue) {
for (int i = 0; i < input.length; i++) {
for (int j = 1; j < input.length; j++) {
if (input[i] + input[j] == targetValue) {
return true;
}
}
}
return false;
}
In the above solution, we looped over the input array twice to get all possible combinations. We checked the combination sum against the target value and returned true if it matches. The time complexity of this solution is O(n^2).
Now let’s see how can we apply the two-pointer technique here:
public boolean twoSum(int[] input, int targetValue) {
int pointerOne = 0;
int pointerTwo = input.length - 1;
while (pointerOne < pointerTwo) {
int sum = input[pointerOne] + input[pointerTwo];
if (sum == targetValue) {
return true;
} else if (sum < targetValue) {
pointerOne++;
} else {
pointerTwo--;
}
}
return false;
}
Since the array is already sorted, we can use two pointers. 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. If the sum of the values is less than the target value, we increment the left pointer, and if the sum is higher than the target value, we decrement the right pointer.
We keep moving these pointers until we get the sum that matches the target value or we have reached the middle of the array, and no combinations have been found. *The time complexity of this solution is O(n) and space complexity is O(1)**,* a significant improvement over our first implementation.
4. Rotate Array k Steps
Problem: Given an array, rotate the array to the right by k steps, where k is non-negative. For example, if our input array is [1, 2, 3, 4, 5, 6, 7] and k is 4, then the output should be [4, 5, 6, 7, 1, 2, 3].
We can solve this by having two loops again which will make the time complexity O(n^2) or by using an extra, temporary array, but that will make the space complexity O(n).
Let’s solve this using the two-pointer technique instead:
public void rotate(int[] input, int step) {
step %= input.length;
reverse(input, 0, input.length - 1);
reverse(input, 0, step - 1);
reverse(input, step, input.length - 1);
}
private void reverse(int[] input, int start, int end) {
while (start < end) {
int temp = input[start];
input[start] = input[end];
input[end] = temp;
start++;
end--;
}
}
In the above methods, we reverse the sections of the input array in-place, multiple times, to get the required result. For reversing the sections, we used the two-pointer approach where swapping of elements was done at both ends of the array section.
Specifically, we first reverse all the elements of the array. Then, we reverse the first k elements followed by reversing the rest of the elements. The time complexity of this solution is O(n) and space complexity is O(1).
5. Middle Element in a LinkedList
Problem: Given a singly LinkedList, find its middle element. For example, if our input LinkedList is 1->2->3->4->5, then the output should be 3.
We can also use the two-pointer technique in other data-structures similar to arrays like a LinkedList:
public <T> T findMiddle(MyNode<T> head) {
MyNode<T> slowPointer = head;
MyNode<T> fastPointer = head;
while (fastPointer.next != null && fastPointer.next.next != null) {
fastPointer = fastPointer.next.next;
slowPointer = slowPointer.next;
}
return slowPointer.data;
}
In this approach, we traverse the linked list using two pointers. One pointer is incremented by one while the other is incremented by two. When the fast pointer reaches the end, the slow pointer will be at the middle of the linked list. *The time complexity of this solution is O(n), and space complexity is O(1).*
6. Conclusion
In this article, we discussed how can we apply the two-pointer technique by seeing some examples and looked at how it improves the efficiency of our algorithm.
The code in this article is available over on Github.