Two Pointers Technique
Given an array
Nelements arranged in an ascending order, also given a number
K. Check if their exist two indices such that sum of elements at those indices is equal to
Yesprint those indices accordingly else print
NOTE: If there are multiple such pair
(i, j), print max
jvalue pair and if all
j′s are equal print min
Input : N = 5 , K = 34 A = [12, 14, 16, 17, 20] Output : 1 4 Explanation : elements at index 1 and 4 sum up to give 34 i.e. arr + arr = 34
Naive Solutionwould be to run two nested loops. Outer loop for picking each element one by one and inner loop for picking rest of the elements one by one.
Check for each index if their exists another index such that the values at both the indexes sum up to the required value, these indexes are our required solution.
Time Complexityof naive approach is
The idea is to learn programming languages online and use
Two Pointers Technique, which is really an easy and effective technique typically used for searching pairs in a sorted array.
We take two pointers, one representing the
first elementand another representing the
last elementof the array. Then we add the values kept at both the pointers. If the sum is less than required value, we will shift left pointer to the right by
1or if their sum is greater than the required value we will shift right pointer towards the left by
1, in order to get closer to the required value. We keep on shifting both the pointers till we get the required value or the required value is not present.
Time Complexityof this technique is
NOTE: This technique only works for
Why are we moving left and right in the array?
As the given array is already sorted, lets say
Xis our current sum of first and last element. If we want a value less than
Xwe can decrement our
rightwill point to an element that is less that the previous element. Similarly if we want a value greater than
X, we can simply increment our
1, now this will point to an element that is greater than the last element.
A = [12, 14, 16, 17, 20] K = 30 i = 0 j = 4 A[i] + A[j] = 12 + 20 = 32 Since A[i] + A[j] > K, j-- i = 0 j = 3 A[i] + A[j] = 12 + 17 = 29 Since A[i] + A[j] < K, i++ i = 1 j = 3 A[i] + A[j] = 14 + 17 = 31 Since A[i] + A[j] > K, j-- i = 1 j = 2 A[i] + A[j] = 14 + 16 = 30 Since A[i] + A[j] = K We found out pair and resultant indexes are (1, 2)