• ← Previous
• Next →

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 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 element that smaller than max but largest among all candidates.

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 pointers: a and b. Traverse the array (say arr) (which means run a for loop with i going from 0 to length(arr)-1)
• If arr[i] is greater than a, then b becomes a and a becomes arr[i]
• Else if arr[i] is greater than b, then b becomes arr[i] (this means that arr[i] is smaller than a but is larger than b)

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:

• Have two pointers: one at start and another at end.
• Check the sum of (arr[start]+ arr[end]).
• If the sum is greater than K, then decrement end.
• If the sum is greater less than K, then increment start.
• 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 (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.

• ← Previous
• Next →