Two Pointers

Two Pointers is a technique of solving problems of linear data structure, especially arrays. It helps to solve problems with lesser time complexity and space complexity and simplifies our code. Let us have a look at a few of the basic problems solved using two-pointers to understand the concept better. Ideally, we point to the first and last index of an array or the first and second index of an array to iterate the array and then move the pointers accordingly. The approach followed in the below problems might help us in solving more complex problems with an easier approach.

TO FIND A SORTED ARRAY OF SQUARES OF A SORTED ARRAY

Let us assume that we need to figure out an array of squares of a sorted array in increasing order. For Example, we need to find a sorted array in increasing order for squares of the element of [-5,-3,-1,0,3,4,6]. 

One way to achieve this is to iterate every member of the given array, square it and store it in a result array. Next, we can sort the result array. If we follow this approach, the time complexity will include the time to iterate the array and the time to sort it. 

Two pointers can help us in this case to minimize the time complexity. Let's declare two integers to point to the first and last index of an array as shown in the below figure. We can then declare a result array and iterate it from last to end and for each iteration of the result array; we can check the square of the start and end pointer. Whichever, square value is greater can be filled in the result array and the pointer can be decreased if it was the end pointer or can be increased if it was the start pointer. This will help us in getting the desired result.

In the above figure, the pointers are placed at -5 and 6 and an empty result array is declared. Next, the square value of both the pointers is computed and it is determined that 36 Is bigger than 25. Hence, 36 is stored in the result array and the end pointer is decreased by 1. 

In the next step, we computed the square value of both the pointers again and determined that 25 is bigger than 16. Hence, 16 is placed in the result array and the start pointer is incremented by 1. 

Once we are done iterating all the elements of the result array, we will get the desired sorted result.

TO MOVE ALL THE ENTRIES OF A PARTICULAR VALUE AT THE END OF THE ARRAY

Next, we will try to move all the entries of a particular value to the end of the array. Let us try to move all the "1" from the array [1,1,0,3,2,8,1]. 

An easier way to solve this problem is to create a new array of the same size and insert all the non "1" entries from the original array to the new array by iterating the original array. Once the iteration is completed, we can add 1 to the remaining indexes of the new array to get the desired output.

An efficient way to solve this problem is via the two-pointers approach. Let us have a look at the diagram below to understand the execution flow:

To solve this problem, we can initiate two pointers at the start of the array only, and can execute a loop until the second pointer is less than the size of the array and follow the below logic:

• If the second pointer value is "1", increment the second pointer and continue the loop.
• If the second pointer value is not "1", check the first pointer value and second pointer value. If they are not the same, swap the values.
• Increment both first and second pointer.

This approach will help us save some space complexity as no new array creation will be required and is an efficient way to solve the problem.

HOW TO REVERSE A STRING USING TWO POINTERS

Let's try to reverse a string. The string is nothing but an array of char, we can apply the two-pointers approach to simplify the problem. Let's assume that we have been given a char array ['A','U','T','O','P','A','C','E'] and we need to get reverse the array and obtain ['E','C','A','P','O','T','U','A'].

Let us declare a start pointer and an end pointer in this case. We can run a loop until the start pointer is less than the end pointer and can follow the below logic:

• Swap the start pointer and end pointer values.
• Increase the start pointer by 1 and decrease the end pointer by 1.

The below diagram shows the complete execution for this problem:

The two pointers can be extended to be used as a fast-slow pointer which is explained in detail in our blog Fast-Slow Pointers.