# 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:

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:

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!

## No Comments Yet