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.

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 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:

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:

In two pass, we can do a first pass and find the max. In the second pass, we find the max (by ignoring the previous max). Using two pointers allows us to find the second biggest element in just one pass.

There is another cool approach to finding the second biggest element in an array and that is to use a min-heap with size 2 -- even simple!. The trick is to delete the smaller element from min-heap, if size increases beyond 2. The time-complexity of this approach would be O(Nlog2) but since log2 is constant, the time-complexity would actually be O(N).

Find two elements 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:

Find closest two sum (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 logN to find the closest. But, in two pointers, we just need (O(NlogN) +N) time-complexity. However, here we need (2 * O(NlogN)) time-complexity.

comments powered by Disqus