Crushing Tech Interviews with the Two Pointer Pattern
The two pointer approach is useful when we deal with sorted arrays or linked lists where we need to find a set of elements that fulfil certain constraints.
Given an array of sorted numbers and a target sum, find a pair in the array whose sum is equal to the given target.
A brute force solution to this question would be to:
- Look at each element one by one.
- Iterate through the remaining elements using a second pointer to find the pair with the target sum.
The time complexity would be O(N^2)! We can do better.
One thing to notice is that the array is sorted. So what we can do is add a pointer at the beginning, and one at the end. At every step we will converge to the target by:
- If sum(left, right) > target → move the right pointer one element to the left (
right -= 1). Because the array is sorted, this has the effect of reducing the current sum.
- If sum(left, right) < target → move the left pointer one element to the right (left
+= 1). Because the array is sorted, this has the effect of increasing the current sum.
Heres some python code:
def pair_with_target(arr: List[int], target:int): left_idx = 0 right_idx = len(arr) - 1 while left_idx < right_idx: current_sum = arr[left_idx] + arr[right_idx] if current_sum == target: return [arr[left_idx], arr[right_idx]] if current_sum > target: # Reduce the current sum by moving right_idx to the left right_idx -= 1 else: # Increase the current sum by moving left_idx to the right left_idx += 1 return [-1, -1] # If we don't find a pair
Here's some related questions to put you to the test:
Also there's a list of these sorts of problems here:
Note: These blog posts are based on educative.io/courses/grokking-the-coding-in... Please go ahead and purchase the course if you find these useful!