Handling Two Pointers in C++

So, two-pointer ( or N pointer for that matter ) is usually a really clever optimization on some brute force approaches in certain conditions.

Let us start looking at this with the help of a question. Then we will generalize our approach.

Question 1:

Given a sorted array A ( sorted in ascending order ),
find if there exists 2 integers A[i] and A[j] such that A[i] + A[j] = 0, i != j

Now the naive solution would be,

This solution is O(n²).

However, let us now analyze how ‘i’ and ‘j’ move with iterations.
Clearly, ‘i’ moves forward with every iteration.
Now let us analyze the ‘j’ loop.
As i is increasing, A[i] is also increasing.
That means the point where the loop breaks is decreasing.
Let us rewrite the 2 loops slightly differently.

Still O(n²).

With the same analysis, as ‘i’ increases, A[i] also increases.
And the number of iterations after which ‘j’ breaks also increases.
But note what changes when ‘i’ moves to i + 1:

• If A[i] + A[J] > 0,
• Then A[i + 1] + A[J] is also greater than 0, as A[i + 1] > A[i].
  This means if we have tried J for ‘i’, then when moving to i + 1, we should only try values of j < J.
  This concludes that our ‘j’ should be monotonically decreasing, and we could re-write the above solution as :

Let us analyze the time complexity of the above solution.
Let us say A.size() = n.

• ‘i’ moves in a total of n steps.
• ‘j’ also moves in a total of n steps
  ( j– is executed at most n times. Note that we are never increasing the value of j. Neither are we resetting it ).

That means we take in a total of n + n steps = O(n).

In general, all two pointer approach work similarly. You look at the naive solution involving multiple loops, and then you start analyzing the pattern on each loop.
Try to look for monotonicity in one of the loops as other loops move forward if you find that you have found your optimization.

Sorting Questions

Question 2: Pair With Given Difference

Given a one-dimensional unsorted array A containing N integers.

You are also given an integer B, find if there exists a pair of elements in the array whose difference is B.

Example Input

Input 1:

A = [5, 10, 3, 2, 50, 80]
B = 78

Input 2:

A = [-10, 20]
B = 30

Example Output

Output 1:

1

Output 2:

1

Example Explanation

Explanation 1:

Pair (80, 2) gives a difference of 78.

Explanation 2:

Pair (20, -10) gives a difference of 30 i.e 20 - (-10) => 20 + 10 => 30

Solution

Method 1: Brute Force
The simplest method is to run two loops, the outer loop picks the first element (smaller element), and the inner loop looks for the element picked by the outer loop plus B.
The time complexity of this method is O(N^2). This will not work. Lets us look at an optimized method.

Method 2: Sorting + Binary Search
We can use sorting and Binary Search to improve time complexity to O(NLogN).

1. The first step is to sort the array in ascending order.
2. Once the array is sorted, traverse the array from left to right, and for each element A[i], binary search for A[i] + B in A[i+1..n-1]. If the element is found, return 1.
3. Both the first and second steps take O(NLogN). So overall complexity is O(NLogN).

Time Complexity : O(NlogN + NlogN)

Method 3: Sorting + Two Pointers
The second step of the above algorithm can be improved to O(N). The first step remains the same.
Let us first look at why the 2 pointer approach works here.
A naive 2 loop approach would be:

for (int i = 0; i < len; i++) {
  for (int j = i + 1; j < len; j++) {
    if (A[j] - A[i] > diff) break; // No need going forward as the difference is going to increase even further. 
    if (A[j] - A[i] == diff) return true; 
  }
}

Now, let us say that for i = I, we keep exploring j.

• At j = J — 1, our difference D1 was less than diff.
• At j = J, our difference D2 exceeded diff.

When i = I + 1, our A[i] increases ( as the array is sorted ).
So, for j = J — 1, the difference will be smaller than D1
(which is, even more, smaller to diff.)
This means we do not need to explore j <= J — 1
and we can begin exploring directly from j = J.
So, j only keeps moving in forward direction and never needs to come back as i increases.

Let us use that in a solution now:

int j = 0; 
for (int i = 0; i < len; i++) {
  j = max(j, i+1);
  while (j < len && (arr[j] - arr[i] < diff)) j += 1;
  if (arr[j] - arr[i] == diff) return true;
}

Time Complexity : O(NlogN + N)

If Array were already sorted, it would also lead to O(N) time complexity. Thus, use this method if the Array is sorted and space complexity optimization is required since it does not require additional space.

int Solution::diffPossible(vector<int> &a, int k) 
{
    int i=0,j=1;
    while(i<a.size() && j<a.size())
    {
        if(i!=j && a[j]-a[i]==k)
        {
            return 1;
        }
        else if(a[j]-a[i]<k)
        {
            j++;
        }
        else
        {
            i++;
        }
    }
    return 0;
}

Method 4: Hashing
Create an empty hash table HT. Traverse the array, use array elements as hash keys and enter them in HT.
Traverse the array again look for value B + A[i] in HT.
Time Complexity: O(N) if we use unordered_map

But it would also lead to O(N) additional space complexity. Thus, use this method if the Array is unsorted and space complexity optimization is not required.

Two Pointer Tricks

Question 3: Maximum Ones After Modification

Problem Description

Given a binary array A and a number B, we need to find the length of the longest subsegment of ‘1’s possible by changing at most B ‘0’s.

Example Input

Input 1:

A = [1, 0, 0, 1, 1, 0, 1]
 B = 1

Input 2:

A = [1, 0, 0, 1, 0, 1, 0, 1, 0, 1]
 B = 2

Example Output

Output 1:

4

Output 2:

5

Example Explanation

Explanation 1:

Here, we should only change 1 zero(0). Maximum possible length we can get is by changing the 3rd zero in the array,
 we get a[] = {1, 0, 0, 1, 1, 1, 1}

Explanation 2:

Here, we can change only 2 zeros. Maximum possible length we can get is by changing the 3rd and 4th (or) 4th and 5th zeros.

Solution

We can solve this problem using two pointers technique.
Let us take a subarray [l, r] which contains at most k zeroes

Let our left pointer be l and right pointer be r. We always maintain our subsegment [l, r] to contain no more than k zeroes by moving the left pointer l.
Check at every step for maximum size (i.e, r-l+1).

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

int solve(vector<int> &A, int B) {
 int n=A.size();
    int l=0, i=0, count=0;
    int ans=INT_MIN;
    for(int i=0;i<n;i++){
        if(A[i]==0){
            count++;
        }
        while(count>B){
            if(A[l]==0)count--;
            l++;
        }
        ans=max(ans, i-l+1);
    }
    return ans;
}

Multiple Array Questions

Question 4: Intersection Of Sorted Arrays

Find the intersection of two sorted arrays.
OR in other words,
Given 2 sorted arrays, find all the elements which occur in both the arrays.

Input : 
    A : [1 2 3 3 4 5 6]
    B : [3 3 5]
Output : [3 3 5]
Input : 
    A : [1 2 3 3 4 5 6]
    B : [3 5]
Output : [3 5]

Solution

Let us name array1 as A and array2 as B, each with sizes ‘m’ and ‘n’.

The obvious brute-force solution is to scan through each element in A, and for each element in A, scan if that element exists in B.
The running time complexity is O(m*n).

First of all, we know that both arrays are sorted.
Can we somehow use this information to our advantage?

We can apply a binary search to find out if an element of A exist in B.
So, the only modification from the brute-force approach is modifying linear search to binary search.
This seems like a good improvement. We manage to reduce the complexity to O(m*log(n)).

Of course, you know you can trade space for running time by using a hash table. Is it beneficial? We can definitely hash each element in B to an array index (takes O(n) time).

Therefore, to find if an element of A exists in B, it would require just O(1) time. The complexity improves to O(m+n).

But there is a problem.
What if n is huge? (i.e., n is one billion!).
The hash table will either require a large amount of memory space or lots of collisions in the table, making access time no longer than O(1) time.
Therefore, using a hash table is not a good general solution to this problem. Besides, using a hash table DOES NOT require for the array to be sorted in the first place.

Here is the most important observation to solve this. Both arrays ARE sorted. This provides a significant clue. We must make full use of this information that they ARE, in fact, sorted.

We can have two indices, which both start at zero.
Compare the two first elements of A and B.

• If A[0] is greater than B[0], we increase the index of B by one.
• If B[0] is greater than A[0], we increase the index of A by one.

If they are equal, we know an intersection has occurred, so add it to the list and increment the index of A and B by one.
Once either of the indices reaches the end of A or B, we have found all A and B intersections.

This approach's complexity is still O(m+n), but it does not require any extra space that a hash table requires.
The complexity is O(m+n) because in the worst case, there would be no intersection between the two arrays, and we need to increment the first index a total of m times and increment the second index a total of n times, which is a total of m+n times.

vector<int> intersect(vector<int> &A, vector<int> &B) {
            vector<int> intersection;
            int n1 = A.size();
            int n2 = B.size();
            int i = 0, j = 0;
            while (i < n1 && j < n2) {
                if (A[i] > B[j]) {
                    j++;
                } else if (B[j] > A[i]) {
                    i++;
                } else {
                    intersection.push_back(A[i]);
                    i++;
                    j++;
                }
            }
            return intersection;
        }

Question 5: Merge Two Sorted Lists

Given two sorted integer arrays A and B, merge B into A as one sorted array.

If the number of elements initialized in A and B are m and n respectively, the resulting size of array A after your code is executed should be m + n

Example :

Input : A : [1 5 8]
        B : [6 9]
Modified A : [1 5 6 8 9]

Solution

Use of additional space is allowed. So, maybe you should try collecting the output in a separate array.

Note: You need 2 pointers at the head of each array and you just need to compare the values at the head of the arrays to get the current minimum.

• Since A is sorted, all values after the pointer are going to be bigger.
• Since B is sorted, all values after the pointer are going to be bigger.

All values before the pointer have already been put in the result array.
So, all you need to do is to choose the smaller value from the 2 heads and move on.

void merge(vector<int> &A, vector<int> &B)
{
    
    // O(1) space
    // If all elements of B are placed in array
    // then elements of A are already in place
    
    int i = A.size() - 1; // i pointing to last index of A
    int j = B.size() - 1; // j pointing to last index of B
    
    int lastPos = A.size() + B.size() - 1; // lastPos pointing to last index of merged array A and B
    
    A.resize(A.size() + B.size());
    
    while(j >= 0)
    {
        if(i >= 0 and A[i] > B[j])
            A[lastPos--] = A[i--];
        else
            A[lastPos--] = B[j--];
    }
    
}

Inplace Update Questions

Question 6: Sort by Color

Given an array with n objects colored red, white, or blue,
sort them so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue.

Example :

Input : [0 1 2 0 1 2]
Modify array so that it becomes : [0 0 1 1 2 2]

Solution

There are multiple approaches possible here. We need to make sure we do not allocate extra memory.

Approach 1:

Count the number of red, white and blue balls.
Then in another pass, set initial redCount number of cells as 0, next whiteCount cell as 1 and next bluecount cells as 2.

Note: Requires 2 pass of the array.

Approach 2:

Swap the 0s to the start of the array maintaining a pointer, and 2s to the end of the array.
1s will automatically be in their right position.

void sortColors(vector<int> &A) {
    
    int red =0, blue =A.size()-1, color = 0;
    while(color <= blue)//we arrange 0's and 2's, 1's will already be in place
    {
        if(A[color]==0)
        {
            swap(A[red++],A[color++]);
        }
        else if(A[color]==2)
        {
            swap(A[blue--],A[color]);
        }
        else
        {
            color++;
        }
    }
}

Question 7: Remove Element from Array

Given an array and a value, remove all the instances of that value in the array.
Also, return the number of elements left in the array after the operation.
It does not matter what is left beyond the expected length.

Example:
If array A is [4, 1, 1, 2, 1, 3]
and value elem is 1,
then new length is 3, and A is now [4, 2, 3]

Solution

You need to modify the original array itself. So it would help if you kept current like pointer which will point to the index of the array where you can store the next value.

Maybe you should try maintaining 2 pointers in the array:

• One pointer iterates over the array
• Other pointer only moves when it finds an element different from ‘elem’.

In other words, the second pointer only moves when the first pointer is on an element worth keeping in the final array.

int removeElement(int A[], int n, int elem) {
    int count = 0;
    for (int i = 0; i < n; i++) { 
        if (A[i] == elem) continue;
        else {
            A[count] = A[i];
            count++;
        }
    }
    return count;
}