Search
⌘K
Get Premium
Two Pointers
Two-Pointer Overview
Count: 10
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.
Try these examples:
Visualization
Python
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
two sum naive
0 / 11
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 unnecessary 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
Try these examples:
Visualization
Python
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
two sum algorithm
0 / 7
Summary
- The two-pointer technique leverages the fact that the input array is sorted to eliminate the number of pairs we consider from O(n2)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:
Done | Question | Difficulty |
|---|---|---|
Medium | ||
Medium | ||
Medium |
Bonus: Additional Problems
These problems also use two pointers in an array, but instead, each pointer represents a logical "region" of the array.
Done | Question | Difficulty |
|---|---|---|
Easy | ||
Medium | ||
Hard |
Mark as read
Unlock Premium Coding Content
Reading Progress
On This Page
Your account is free and you can post anonymously if you choose.