In the two pointers approach we maintain two pointers (generally denoted by l and r) in a monotonic interval (usually a sorted array) to find two values which sum to a number for example. A general problem of this category could be to find all pairs of two values which sum to a given number.
Let’s take an example to understand this more clearly:
E.g: arr[] = { 1, 2, 3, 4, 5, 6 } Note: Here the array is sorted
Now, you will be asked to find is there any pair in the given array, with
some sum let’s take
sum = 7, which obviously exist in given array as a pair of {1,6}, {2,5}, {3,4}
So, let’s first see how we can achieve it using brute force. Could you implement brute force? Before going through our solution, believe me it’s super easy and you can do it easily.
· We iterate over all possible pairs leading to an O(n*n) solution: -
Time Complexity = O(n^2)
· In this approach we let the left pointer be 0 and right pointer be n-1.
· We need the array to be sorted so we sort it first.
· If A[l]+A[r] is greater then sum we need to decrease the right pointer. This is because if we increased l anymore the current sum would always be greater than sum
· Similarly, if A[l]+A[r] is lesser than sum we need to increase the left pointer. This is because if we decrease r anymore the current sum would always be lesser than sum.
· However if A[l]+A[r] is equal to the sum we need to decrease the right pointer and increase the left pointer.
· We repeat this until l becomes equal to r since then l and r will cross each other.
below is the implementation of Two-Pointer Approach in C++
Time Complexity = O (n log n) for sorting and O (n) for two pointers
Try solving below problems, as this will make your newly learned concept more concrete :
1. https://www.codechef.com/problems/NOTALLFL
2. https://www.hackerrank.com/challenges/angry-children/problem
3. https://www.spoj.com/problems/INC2015F/
Happy Coding 😊
By Programmers Army
Contributed by: Adhish Kancharla