Two Pointers
Two-pointer triggers: The input consists of one or two arrays/strings/linked lists. We need to use O(1) extra memory or modify the input in place. The input is sorted. The naive solution is and we want to get to .
Key Variations
There are generally three main ways to use the two pointers technique:
1. Inward Pointers (Converging)
One pointer starts at the beginning (left = 0) and the other at the end (right = n - 1). They move towards each other.
- When to use: Searching for a pair in a sorted array, checking for palindromes, reversing a string/array.
- Termination: Usually when
left > right.
2. Slow and Fast Pointers (Same Direction)
Both pointers start at the beginning, but one moves faster than the other.
- When to use: Cycle detection in linked lists (Floyd's Cycle Finding Algorithm), removing duplicates in-place, sliding windows.
- Termination: Usually when the fast pointer reaches the end.
Recipe: Seeker and Writer
In-place compaction
Read every value once. Write only the values you want to keep.
seekerReadsScans each input position and always moves forward.
writerWritesMarks the next output position and moves only when a value is kept.
Loop invariant
arr[:writer] contains exactly the kept values seen so far.
seeker, writer = 0, 0
while seeker < len(arr):
if should_keep(arr[seeker]):
arr[writer] = arr[seeker]
writer += 1
seeker += 1
return writerwriter = new lengthO(n) timeO(1) extra space3. Parallel Pointers
Two pointers move in lockstep through separate inputs or non-overlapping regions.
- When to use: Merging sorted arrays, finding intersections, or pairing corresponding regions.
- Termination: Usually when one pointer reaches the end of its input or region.
Why Use It?
- Time Complexity: Often reduces a nested loop solution to a single pass .
- Space Complexity: Usually efficient constant space, as it only requires two variables.
Practice Problems
Valid Palindrome
A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.
Two Sum II - Input Array Is Sorted
Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.
Remove Duplicates from Sorted Array
Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.
Container With Most Water
You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).
Squares of a Sorted Array
Given an integer array nums sorted in non-decreasing order, return *an array of the squares of each number sorted in non-decreasing order*.
Interval List Intersections
You are given two lists of closed intervals, firstList and secondList, where firstList[i] = [start_i, end_i] and secondList[j] = [start_j, end_j]. Each list of intervals is pairwise disjoint and in sorted order.
Merge Sorted Array
You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.
Parity Sorting
Given an array of integers arr, modify it in place to put all even numbers before all odd numbers. The relative order between even numbers does not matter. Same for the odd numbers.
Quicksort Partition
Given an array of integers arr and a number pivot, modify arr in place using only O(1) extra space so that:
Dutch Flag Problem
Given an array consisting of letters 'R', 'W', and 'B', sort it in place to put all the 'R' before all the 'W' and all the 'W' before all the 'B'.
Prefix-Suffix Swap
We are given an array of letters, arr, and a length, n, which is a multiple of 3. The goal is to modify arr in place to move the prefix of length n/3 to the end and the suffix of length n/3 to the beginning.
Shift Word to Back
You are given an array of letters, arr, and a string, word. We know that word appears within arr as a subsequence. Identify the earliest occurrence of word in arr and move all those letters, in order, to the end of arr. You must do this in place.