## Two-Pointer Technique

This technique refers to using two pointers that start at opposite ends of an array and gradually move towards each other.

In this page, we'll cover:

- A simple problem that illustrates the motivation behind the two-pointer technique.
- The types of problem for which you should consider using this technique.
- A list of problems (with animated solutions!) for you to try that build upon the concepts covered here.

## Problem: Two Sum

###### DESCRIPTION

Given a **sorted array** of integers nums, determine if there exists a pair of numbers that sum to a given target.

**Example**:
Input: nums = [1,3,4,6,8,10,13], target = 13
Output: True (3 + 10 = 13)

Input: nums = [1,3,4,6,8,10,13], target = 6 Output: False

The naive approach to this problem uses two-pointers i and j in a nested for-loop to consider each pair in the input array, for a total of O(n2) pairs considered.

def isPairSum(nums, target):for i in range(len(nums)):for j in range(i + 1, len(nums)):if nums[i] + nums[j] == target:return Truereturn False

However, if we put a bit more thought into how we initialize our pointers and how we move them, we can **eliminate the number of pairs we consider down to O(n)**. Understanding why we are able to eliminate pairs is key to understanding the two-pointer technique.

### Eliminating Pairs

The two-pointer technique leverages the fact that the input array is sorted.

Let's use it to solve the Two Sum problem when nums = [1, 3, 4, 6, 8, 10, 13] and target = 13.

We start by initializing two pointers at opposite ends of the array, which represent the pair of numbers we are currently considering.

This pair has a sum (14) that is greater than our target (13). And because our array is sorted, **all other pairs ending at our right pointer (13) also have sums greater than our target**, as they all involve numbers greater than 1, the value at our left pointer.

So, to move onto the next pair we **move our right pointer back**, which elimininates those unecessary pairs from our search.

Now, since our sum is **less than** our target, we know that all other pairs involving our left pointer also have sums less than our target. So, we move our left pointer forward to eliminate those unnecessary pairs and arrive at the next pair to consider.

This continues until either our pointers meet (in which case we did not find a successful pair) or until we find a pair that sums to our target, like we did here.

### Solution

def twoSum(nums, target):left, right = 0, len(nums) - 1while left < right:current_sum = nums[left] + nums[right]if current_sum == target:return Trueif current_sum < target:left += 1else:right -= 1return False

### Summary

- The two-pointer technique leverages the fact that the input array is sorted to eliminate the number of pairs we consider from O(n
2)down to O(n). - The two-pointers start at opposite ends of the array, and represent the pair of numbers we are currently considering.
- We repeatedly compare the sum of the current pair to the target, and move a pointer in a way that eliminates unnecessary pairs from our search.

## When Do I Use This?

Consider using the two-pointer technique for questions that involve searching for a pair (or more) of items in an array that meet a certain criteria.

*Examples:*

- Finding a pair of items that sum to a given target in an array.
- Finding a triplet of items that sum to 0 in a given array.
- Finding the maximum amount of water that can be held between two array items representing wall heights.

## Practice Problems

Try applying the concepts related to eliminating unnecessary pairs to the following problems:

Question | Difficulty |
---|---|

Container With Most Water | Medium |

3-Sum | Medium |

Triangle Numbers | Medium |

## Bonus: Additional Problems

These problems also use two pointers in an array, but instead, each pointer represents a logical "region" of the array.

Question | Difficulty |
---|---|

Move Zeroes | Easy |

Sort Colors | Medium |

Trapping Rain Water | Hard |

Loading comments...