Identifying direct application
The two-pointer technique can be applied directly only to a subset of problems that fall under the two-pointer pattern. These are generally easy problems in which we must simultaneously traverse an array in both directions and meet in the middle. If the problem statement or its solution follows the generic template below, it can be solved by applying the two-pointer technique directly.
Given an array
arr perform some operations on arr[i] and arr[j] such that i < j and with each iteration, i and j move closer to each other by some steps. Both i and j may start from some arbitrary indices x and y in the array such that x < y.Example
To better understand the problems that can be solved by directly applying the two-pointer technique, let's consider the following problem and see how we can identify it as a direct application of the two-pointer technique.
Problem statement: We are given an array `arr` and we have to reverse it in-place. An in-place reversal means we must modify the original array and not create and return a new one.
Reverse the given array in place
Brute force solution
The brute-force solution to this problem is to traverse the array in the reverse direction (from end to start) and copy the items to temp array. Next, we traverse the temp array in the forward direction (from start to end) and copy the items to the original array.
Reverse an array in-place by copying to temp array
The implementation of the brute force solution is given as follows.
C++
Java
Typescript
Javascript
Python
While the solution is correct, it requires two traversals and additional space for the temporary array. Let's now look at the two-pointer solution to this problem
Two pointer solution
We can reverse the array in-place by swapping equidistant elements from both ends. This solution would require traversing the array simultaneously from both ends, fitting the generic template for the direct application of the two-pointer technique.
Given an array (
arr) perform some operations (swap) on arr[i] and arr[j] such that i < j and with each iteration, i and j move closer to each other by some steps (1 step each). Both i and j may start from some arbitrary indices x (0) and y (arr.length - 1) in the array such that x < y.We create two variables, left and right, and initialize them with 0 and the n-1 where n is the size of the array. We then iterate until left is greater than right, and in each iteration, swap the items at these indices, increment left , and decrement right by 1. At the end of all iterations, when left and right meet each other, the array is reversed in place.
Below is an execution of the two-pointer solution to reverse an array in-place.
Reverse an array in-place using the two-pointer technique
The implementation of two-pointer solution is given as follows.
C++
Java
Typescript
Javascript
Python
As the code above demonstrates, using the two-pointer technique, we reverse the array in place in a single pass without using any extra space.
Example problems
Most problems that fall under this category are easy problems; a list of a few is given below.
We will now solve these problems to better understand the direct application of the two-pointer technique.