Two Pointers Technique

 ☝Two Pointers☝ 

technique

Objectives:

After reading (as well as practicing) this, you shall :

• have a better understanding of the two pointers method to solve array based problems.
• be able to give more efficient solution for some array based problems which were earlier taking higher time and space complexities.
• solve some easy and medium level questions on this topic. (leetcode difficulty scale)

Pre-Requisites:

• Basic C++ syntax
• Arrays and vectors in CPP
• Basic knowledge about time and space complexities (Big' Oh Notation)
• Will to Learn

The "Two pointers is an easy and effective technique that is typically used for searching element pairs in a array that satisfy a certain condition." 

Term 'two pointer' doesn't mean the pointer type variables that we declare to store addresses. But it refers to two variables that points to two different index in an array, to compare the elements at those positions. It is not that, we have to use two pointers strictly, we can use more than two, i.e. three, four or even one pointer. 

A Few Points to you must be clear of:

• Decide carefully whether your pointers refer to a range or pairs.
• How to initialize the pointers. For eg. Both from same side growing in same direction or from opposite sides growing in opposite direction
• How and when the pointers are shifted. For Eg. there are questions having one pointer incrementing by 2 and other by 1, or the pointer having higher element is shifted etc.
• Ending condition of the loop.

Whenever in a problems of arrays you have to deal with pairs. You can think of the TWO POINTERS approach. But there can be other ways too.

Here I will explain the Two Pointer method by solving some mostly asked questions. In first few problems I will also show brute force method and gradually reach optimal solution using two pointer technique.

PORBLEM 1: Given an array of 0's and 1's only. Sort 0's and 1's (first 1 then 0).

One of the methods can be :

1. Declare two variables , to count number of zeros and number of ones.
2. Traverse the array ones to count number of zeroes and number of ones.
3. Then again traverse the array putting that many ones first and then that many zeros.

Time complexity : O(2 x n) => O(n)           Space complexity : O(1)

Better solution can be obtained by traversing the array only once using two pointers (i, j):

1. Initialize two pointers i = 0, j = size-1.
2. start While (i<j)
3. if arr[i] == 0 and arr[j] = 1
4. then swap(arr[i], arr[j]);
5. if arr[i] == 1 then i++;
6. if arr[j] == 0 then j--;
7. end while loop.

Time Complexity: O(n)                        Space Complexity: O(1)

Similar question 1: Sort even and odd numbers in an array. Relative order restored. (1st even then odd). "Sort Array by Parity"

What's new in the solution is => "Bit Manipulation"

Using the and operation, we can check if a number x is even because x&1= 0 if x is even, and x&1 = 1 if x is odd. More generally, x is divisible by 2^k exactly when x&(2^k −1) = 0.{even numbers will always have a 0 at their LSB}

Similar question 2: "move all zeroes to end of the array"

PORBLEM 2: "Pair With a given sum in a Sorted array" 

The most Brute Force method we can think of is fixing one element of the array and then searching for its sum pair in the rest elements.

Time Complexity: O(n²)                        Space Complexity: O(1)

The above approach can be used for both sorted and unsorted arrays.

Now using TWO POINTER technique. (will work for sorted arrays)

1. We will take two pointers i, j;
2. initialize i = 0, j = size-1;
3. start while(i<j)
4. if(arr[i] + arr[j] == sum) then count++, i++, j--;
5. else if(arr[i] + arr[j] < sum) then i++; //Array being sorted in increasing order we will get higher values going right.
6. else j--;
7. end loop

Time Complexity: O(n)                         Space Complexity: O(1)

If the array is not sorted then first sort the array then apply the above steps. Consider the question: "Max Number of K-Sum Pairs"

Time Complexity: O(nlogn)                     Space Complexity: O(1)
* better solutions may be possible for the above question

PORBLEM 3: Given three sorted arrays A, B, and C of not necessarily same sizes. Calculate the minimum absolute difference between the maximum and minimum number of any triplet A[i], B[j], C[k] such that they belong to arrays A, B and C respectively, i.e., minimize (max(A[i], B[j], C[k]) – min(A[i], B[j], C[k]))

Most Brute force solution can be fixing one element of A and then for that fix another element of B and then for that fix another element of C.

Time Complexity: O(n³)                        Space Complexity: O(1)

See in the brute force the unwanted cases are when we are having the min among the three and max among the three but we are changing the element other than these two.

Now using TWO POINTER technique we will make only effective changes.

• Start with the largest elements in each of the arrays A, B & C. 
• Maintain a variable to update the answer during each of the steps to be followed.
• In every step, the only possible way to decrease the difference is to decrease the maximum element out of the three elements.
• So traverse to the next largest element in the array containing the maximum element for this step and update the answer variable.
• Repeat this step until the array containing the maximum element ends.

Time Complexity: O(n)                         Space Complexity: O(1)

PORBLEM 4: "Container With Most Water" 

Without discussing about the Brute Force, coming directly to the optimized solution using TWO Pointer.

1. Initialize two pointers i = 0, j = size-1, ans with a lower value;
2. Start loop till (i<j)
3. Find capacity and update ans if required in each step.
4. Shift the pointer of the lower height.
5. End Loop.