Two pointers concept

By hearing the name “pointer”, you might think that we are gonna use the concept of the pointer in C. But it is not. Here two pointers indicate two variables. It works for sorted arrays to find pairs in an array.

Algorithm:

• One variable at index 0 and the other at index n-1.
• We have to add these 2 elements.
• If it is equal to the sum, then it is a pair
• If it is greater than the sum, decrement the right index and add two elements. Since it is a sorted array, if we decrement it, then the value may be less than or equal to the sum.
• If it is less than the sum, increment the left index. As we come forward in a sorted array, the value will be increased.

This idea is a two pointers concept. Let’s get into detail with one example.

Example :

Find the count of pairs which is equal to sum

Given : arr[] = {1,2,3,4,5,6}

Sum = 6

Steps:

Output: 2

Code:

Space Complexity: O(1)

Time Complexity: O(nlogn)

Note: If they mention in question that the given array will be in sorted order, then we no need to sort the array. So at that time, time complexity will be O(n).

In the above case, I assumed that the array is not sorted. Therefore, the time complexity is O(nlogn).