Two Pointers
Use two indices that move toward each other or in the same direction to solve problems on sorted arrays or when looking for pairs/triplets that satisfy a condition.
Time
O(n)
Space
O(1)
Recognize it when
- Sorted array with pair/triplet sum problem
- Remove duplicates in-place
- Palindrome check
- Partition or rearrange array in-place
Questions — ordered by difficulty
Valid Palindrome
A string is a palindrome if, after removing non-alphanumeric characters and lowercasing, it reads the same forward and backward.
Two Sum II - Input Array Is Sorted
Find two numbers in a sorted array that add up to a target. Return their 1-indexed positions.
Remove Duplicates from Sorted Array
Remove duplicates from a sorted array in-place and return the count of unique elements.
3Sum
Find all unique triplets in an array that sum to zero.
Container With Most Water
Find two lines that together with the x-axis form a container that holds the most water.
Trapping Rain Water
Given an elevation map, compute how much water it can trap after raining.
Sort Colors
Sort an array of 0s, 1s, and 2s in-place in one pass without using a sort function (Dutch National Flag problem).
Is Subsequence
Given two strings s and t, return true if s is a subsequence of t, or false otherwise.