Introduction to Two pointer approach with example code

Ok, don’t be alarmed. Two pointer is nowhere related to C Language Pointers.

In this context, two pointers simply mean there will be 2 variables that will be pointing to two different index of an array.

Let us understand this approach with help of an example and understand how it will increase the efficiency of the solution.

You are given an array in ascending order and a key element. You need to find 2 elements that add up to the key.

Array  =  [1, 4, 6, 8, 10, 12]

Key = 14

This problem can be solved by 2 methods:

1. Brute force approach

2. Two pointer approach

First we shall solve it with brute force approach, later we will see two pointer solution.

In this approach we use 2 for loop. The elements from the inner loop will be added with outer loop as shown below:

1 + 4 = 5
1 + 6 = 7
1 + 8 = 9
1 + 10 = 11
1 + 12 = 13

Here we did not find the required pair, we move to the next element from the outer loop. Them we add to all the elements in the inner loop one by one.

4 + 6 = 10

4 + 8 = 12

4 + 10 = 14

We got the pair.

Here by using brute force approach, at the worst case we will have O(n^2). Which takes lot of time for large number of values.

In the two pointer approach, one variable will be pointing at the starting index and another variable will be pointing at the ending index.

It can be visualized as below:

 Now we got 2 elements from the 2 pointers. Now we add them and check if the sum value is equal to the key.

 If not, we move any one of the pointer based on below rules:

Here the sum is 13. As the sum is less than key value, increase L index.

Here the sum is 16. As the sum is greater than the key, decrease R index.

As the sum value is 14, that is equal to the key element. We exit the loop.

As you can see, it can be done using only one loop, hence at worst case, it can be done in O(n) time.

#include<iostream>
#include<vector>

using namespace std;

void brute_force_approach(vector<int> arr, int key)
{
	for(int i = 0; i < arr.size(); i++)
	{
		for(int j = i; j < arr.size(); j++)
		{
			if(arr[i] + arr[j] == key)
			{
				cout<<"Elements Found"<<endl;
				return;
			}
		}
	}

	cout<<"Elements NOT Found"<<endl;
	return;
}

void two_pointers_approach(vector<int> arr, int key)
{
        int left = 0;
        int right = arr.size() -1;

        while(left < right)
        {
            if(arr[left] + arr[right] == key)
            {
				cout<<"Elements Found"<<endl;
                return;
            }
            else if(arr[left] + arr[right] > key)
            {
                right--;
            }
            else
            {
                left++;
            }
        }

        cout<<"Elements NOT Found"<<endl;
		return;	
}

int main()
{
	vector<int> arr;
	arr.push_back(2);
	arr.push_back(3);
	arr.push_back(6);
	arr.push_back(7);
	arr.push_back(8);
	arr.push_back(9);

	int key = 13;

	brute_force_approach(arr, key);
	two_pointers_approach(arr, key);

	return 0;
}

Elements Found

Elements Found