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:

leetcode.com/problems/squares-of-a-sorted-a.. (Easy) leetcode.com/problems/3sum (Medium) leetcode.com/problems/sort-colors (Medium)

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!