Two Pointer technique is used for solving problems that require searching for pairs or triplets in an array. There are various
applications of two pointers.
Reversing an array
Here are the high-level steps to reversing an array and this is an in-place reversal.
- Have two pointers: one at start and another at end.
- Swap the two. Then increment start, decrement end (till start < end).
The brute force would be to have a new array and copy elements form back. But, using just an extra pointer, we are able to reverse the array in-place and thus, save O(N) space.
Find the second biggest element in an array
It is easy to find this in two-pass. We can do that as follows:
- In the first pass, find the maximum (say max).
- In the second pass, find the largest element that is smaller than max.
The trick is to find this in a single-pass. We can do that with two pointers and thereby, find the second biggest element just in one pass. Here are the steps:
- Keep two variables (pointers): max_1 and max_2, where max_1 is the biggest element and max_2 is the second biggest.
- Traverse the array (say arr) (which means run a for loop with i going from 0 to length(arr)-1). Compare arr[i] with max_1.
- If arr[i] is greater than max_1, then arr[i] is a candidate for max_1. Set max_2 to max_1 and set max_1 to arr[i].
- Else if arr[i] is greater than max_2, then max_2 becomes arr[i] (this means that arr[i] is smaller than max_1 but is larger than max_2)
Thus, using two pointers allows us to find the second biggest element in just one pass.
While we are at it, there is another cool and simpler approach to finding the second biggest element in an array and that is to use a min-heap with size 2!. In this approach,
- We traverse the array and keep adding elements to the min-heap as long as it is greater than the smallest one in the heap and thus, we accumulate bigger numbers in the heap.
- We heap size increases more than 2, then the trick is to delete the smaller element from min-heap; since the smaller number would be at the root, it is easy to delete the smaller number.
The time-complexity of this approach would be O(Nlog2) but since log2 is 1 (with base as 2), the time-complexity would actually be O(N) which would be same as a single pass!
Find two elements in a sorted array that add up to a sum (say K)
The goal is to find two elements that add up to K in a sorted array (arr).
The brute-force approach would be to run two for-loops (i and j) and check if the sum matches K or not. However, this approach would be O(N^2). Instead, we can use two pointer will also allow us find all pairs that add up-to K. Here is how we can do that:
- Have two pointers (array indices): one at start (index 0) and another at end (index arr.length-1).
- Check the sum of (arr[start]+ arr[end]).
- If the sum is greater than K, then we need to go lower. We do that by decrementing end since we want a lower value for sum and clearly, arr[end] is lower (since the array is sorted).
- If the sum is less than K, then we need to go higher. We do that by incrementing start since we want a higher value for sum and clearly, arr[start] is higher (since the array is sorted).
- If the sum is equal to K, then you have found your match!
- Else, keep doing this till start < end. If we did not find any match, then such two elements do not exist.
Find closest two sum in an unsorted array (say K)
The approach here is to sort the array and use two pointers. Similar to finding two sum (see above). Along the way, you would either find K or the two elements that are closest to K. This will also allow us find all pairs that are closest.
Alternatively, we can also sort the array and for each element, we use another a binary search (which costs logN) to find the closest. But, in two pointers, we just need (O(NlogN) +N) time-complexity (O(NlogN) to sort and O(N) to traverse the array). However, here we need (2 * O(NlogN)) time-complexity (O(NlogN) to sort the array and do binary search (log(N)) for all N elements).
Also, if the array is already sorted, then we can use two-pointers to find the closest two sum in O(N) and we can use binary search at each element to find the closest sum in O(NlogN).