Two Pointers Technique in C++

Hello friends, In this tutorial, we will see what is two pointer technique in C++ and how it can be used to solve some problems like finding if the two elements of a sorted array can sum to a target.

C++: Two Pointer Technique

Let’s take a sorted array arr[6] = {1,3,7,8,10,13} and we want to find if the sum of any two-element can be target sum(let’s take 9 ). Now a naive approach to handle this problem is using two loops and we check the sum of each pair of elements and see if it is equal to the target sum. In this example, we can make 9 using 1 and 8 from the given array.

Code for the naive approach:

#include<bits/stdc++.h>
using namespace std;

int main()
{
  int n = 6; // array size

  int arr[n] = {1 , 3, 7, 8, 10, 13 };

  int target_sum = 9;

  bool possible = false;

  int i,j;
  for( i = 0 ; i < n ; i++ )
  {
    
    for( j = i+1 ; j<n ; j++ )
    {
      if( arr[i] + arr[j] == target_sum)
      {
        possible = true;
        break;
      }
    }

    if(possible == true) break; // we have got a pair that sums to target_sum
  }


  if(possible)
  {
    cout<<"index1 : "<<i<<" , index2 : "<<j<<endl;

    cout<<"value at index1 : "<<arr[i]<<endl;
    cout<<"value at index2 : "<<arr[j]<<endl;
  }
  else
  {
    cout<<"No two elements sums to the given target\n";
  }
}

Output:

index1 : 0 , index2 : 3
value at index1 : 1
value at index2 : 8

Time Complexity of this approach is O(n*2). Can we do it better? Yes using the two-pointer approach.

Here we maintain two-pointer i that starts from left end and increases and the other pointer is j that starts from the right end and decreases. At each iteration, we maintain the sum of values at these two pointers. If this sum is greater than the target sum we decrement j(right pointer ) as the values in right to left direction decreases and if it smaller we increment i (left pointer )  as value increases in the left to the right direction. Once we hit the target sum we stop.

Code using the two-pointer technique:

#include<bits/stdc++.h>
using namespace std;

int main()
{
  int n = 6; // array size

  int arr[n] = {1 , 3, 7, 8, 10, 13 };

  int target_sum = 9;

  bool possible = false;

  int i=0; // left pointer
  int j=n-1; // right pointer

  while( i < j && i<=n-1 && j >= 0)
  {
    if( arr[i] + arr[j] > target_sum)
    {
      j--;
    }
    else if( arr[i] + arr[j] < target_sum )
    {
      i++;
    }
    else
    {
      possible = true;
      break;
    }

  }
  


  if(possible)
  {
    cout<<"index1 : "<<i<<" , index2 : "<<j<<endl;

    cout<<"value at index1 : "<<arr[i]<<endl;
    cout<<"value at index2 : "<<arr[j]<<endl;
  }
  else
  {
    cout<<"No two elements sums to the given target\n";
  }
}

Output:

index1 : 0 , index2 : 3
value at index1 : 1
value at index2 : 8

Time Complexity of this solution is O(n).

Leave a Reply

Your email address will not be published. Required fields are marked *