Quick Interview Crack (Two Pointers Technique)

Two pointer technique is commonly used to find a specific pairs of an sorted array or update respectively.

It is basically searching in an array using two pointers. One at the beginning and one at the end.

Let's look at a commonly given interview problem. Suppose, an array and an integer is given and we have to find a pair from the given array which sum is equal to the given integer.

In order to find the pair first we need to sort the array. Then set two pointers and check if sum of their value is equal to the given integer or not. If yes, return the pair. Otherwise, if sum is greater than target, decrement the end pointer else, increment the beginning pointer. End the loop if the pointers meet together. Pseudo code is given below for better understanding.

array.sort()
initialising Pointer One = 0
initialising Pointer Two = size of array - 1
while pointer one is not pointer two {
    sum = sum(array[pointer one], array[pointer two])
    if sum == target {
        return array[pointer one], array[pointer two]
    } else if sum<target {
        increment pointer one  
    } else {
        decrement pointer two
    }
}

Time Complexity:
For sorting the given array, time complexity is O(NlogN). And searching for pairs using two pointers, O(N).

Total time complexity: O(NlogN) + O(N) = O(NlogN)