TWO POINTER ALGORITHM
used to find elements of a array which sum up to some desired value.
Suppose you have 2 arrays A and B and you need to find if there exists some i and j in A and B respectively such that A[i] + B[j] = val, where val is some value given to you.
We make use of 2 pointers p1 and p2. Firstly, sort the 2 arrays using a suitable sort algorithm. This takes O(n log n) time each.
Initially p1 points at index 0 of array A and pointer p2 points at index n-1 of array B. Now we run the following inside a while loop
1.calculate A[p1]+B[p2]
2.If this value is greater than val then we do p2--.
2.If this value is greater than val then we do p2--.
3.If this value is smaller than val then we do p1++.
4.Else if this value is equal to val then p1 and p2 point to the elements of the two arrays whose sum is equal to val and we can break the loop.
5.Exit condition of the loop is specified as when either p1 reaches end of array A or p2 reaches start of array B. If either of the above happens then we have exhausted our search space.
note that we have put the following restriction on p1 and p2. p1 can only move down an array , thus we can only increment it. p2 can only move up an array, i.e we can only decrement its value.
The above technique can be applied to the spoj problem - love story
4.Else if this value is equal to val then p1 and p2 point to the elements of the two arrays whose sum is equal to val and we can break the loop.
5.Exit condition of the loop is specified as when either p1 reaches end of array A or p2 reaches start of array B. If either of the above happens then we have exhausted our search space.
note that we have put the following restriction on p1 and p2. p1 can only move down an array , thus we can only increment it. p2 can only move up an array, i.e we can only decrement its value.
The above technique can be applied to the spoj problem - love story
