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:

1. Look at each element one by one.
2. 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:

1. 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.
2. 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:

leetcode.com/tag/two-pointers

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!