Practice 10 essential two-pointer problems from easy to hard, with clear reasoning, edge cases, complexity analysis, and Python and Java solutions.
Reverse an array of characters without allocating another array. This is the simplest way to learn how opposite-end pointers work.
Given an array of characters chars, reverse the array in place. You may modify the input, but you must use only constant extra space.
Input: chars = ["h", "e", "l", "l", "o"]
Output: ["o", "l", "l", "e", "h"]Why: Swap the first and last characters, then continue toward the center.
Input: chars = ["A", "B"]
Output: ["B", "A"]chars[i] is a printable character.The character that belongs at the left end is currently at the right end, and vice versa. After those two values are swapped, neither position needs to be visited again.
left to the first index and right to the last index.chars[left] and chars[right].left one step right and right one step left.After each swap, the characters at left and right are in their final reversed positions. The unprocessed interval shrinks by two, so when the pointers meet or cross, every position is correct.
def reverse_string(chars: list[str]) -> None:
left, right = 0, len(chars) - 1
while left < right:
chars[left], chars[right] = chars[right], chars[left]
left += 1
right -= 1
chars = ["h", "e", "l", "l", "o"]
reverse_string(chars)
print(chars) # ["o", "l", "l", "e", "h"]For ["h", "e", "l", "l", "o"], swap indices 0 and 4, then indices 1 and 3. Both pointers then reach the center character, which is already in its final position.
left <= right is safe but performs a needless self-swap for odd-length input; left < right is cleaner.Check whether text reads the same forward and backward while ignoring punctuation, spaces, and letter case.
Given a string s, return true if its alphanumeric characters form a palindrome after letter case is ignored. Otherwise, return false.
Input: s = "A man, a plan, a canal: Panama"
Output: trueWhy: After normalization, the text is "amanaplanacanalpanama".
Input: s = "race a car"
Output: falseWhy: The first mismatch is between the second and second-to-last relevant characters.
s may contain letters, digits, spaces, and punctuation.A palindrome is defined by matching mirrored characters. Two pointers can compare those pairs directly, skipping characters that do not participate in the normalized text.
false on a mismatch.At each iteration, the pointers identify the next outermost pair in the normalized string. A mismatch proves the normalized string is not a palindrome. If every mirrored pair matches, the entire normalized string reads identically in both directions.
def is_valid_palindrome(s: str) ->
Compress a sorted array in place so that each distinct value appears once in the valid prefix.
Given a sorted integer array nums, remove duplicate values in place. Return the number k of unique values; the first k positions of nums must contain those values in sorted order.
Input: nums = [1, 1, 2]
Output: k = 2, nums[:k] = [1, 2]Input: nums = [0, 0, 1, 1, 1, 2, 2, 3]
Output: k = 4, nums[:k] = [0, 1, 2, 3]nums is sorted in nondecreasing order.Because equal values are adjacent in a sorted array, a value is new exactly when it differs from the last value written. The read pointer explores; the write pointer marks the next unique slot.
write at the index of the last unique value.read, starting at index 1.nums[read] differs from nums[write], increment write and copy the new value there.write + 1.Before each read step, positions 0 through write contain every distinct value seen so far exactly once. A duplicate leaves that prefix unchanged; a new value is appended to it. The invariant therefore holds through the final element.
def remove_duplicates(nums: list[int]) ->
Move every zero to the end of an array in place while keeping nonzero values in their original relative order.
Given an integer array nums, move all zero values to the end without changing the relative order of the nonzero values. Modify the array in place.
Input: nums = [0, 1, 0, 3, 12]
Output: [1, 3, 12, 0, 0]Input: nums = [0, 0, 7]
Output: [7, 0, 0]The slow pointer marks the next position that should contain a nonzero value. The fast pointer searches for the next such value. Swapping them compacts nonzero values in encounter order.
write to 0.read.nums[read] is nonzero, swap it with nums[write] and increment write.Before every iteration, the prefix ending before write contains all nonzero elements seen so far in their original order. Processing a zero changes nothing; processing a nonzero appends it to that prefix. Thus the final prefix contains every nonzero value in order and all remaining positions contain zeroes.
def move_zeroes(nums: list[int]) -> None:
write = 0
for read in range(len(nums)):For [0, 1, 0, 3, 12], the fast pointer finds 1, 3, and 12 in that order. Each is swapped into the next write position, producing [1, 3, 12, 0, 0].
Find a target pair in a sorted array in linear time by eliminating impossible pairs after every comparison.
Given a 1-indexed, sorted integer array numbers and an integer target, return the two indices whose values add to target. Exactly one solution exists, and the same element cannot be used twice.
Input: numbers = [2, 7, 11, 15], target = 9
Output: [1, 2]Input: numbers = [-3, 2, 4, 8], target = 5
Output: [1, 4]Why: -3 + 8 = 5.
numbers is sorted in nondecreasing order.The smallest and largest remaining values define a useful boundary. If their sum is too small, the smallest value cannot work with any remaining value; if the sum is too large, the largest value cannot work.
left at the beginning and right at the end.left right when the sum is too small; otherwise move right left.If the current sum is below the target, pairing the left value with any index no larger than right cannot produce a greater sum, so discarding it is safe. The symmetric argument holds when the sum is too large. No possible solution is discarded.
def two_sum_sorted(numbers: list[int], target:
Maximize the area between two vertical lines using a greedy two-pointer decision that is backed by an elimination proof.
Given an array height, where height[i] is the height of a vertical line at index i, choose two lines that hold the most water. Return the maximum area.
Input: height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
Output: 49Why: The lines at indices 1 and 8 have width 7 and limiting height 7.
Input: height = [1, 1]
Output: 1Area equals width times the shorter height. Moving the taller line inward only reduces width while the shorter line still limits the height, so only moving the shorter side can possibly improve the area.
Suppose the left line is no taller than the right line. Any container that keeps the left line and moves the right line inward has less width and a height no greater than the left line, so it cannot improve the current area. Discarding the left line is therefore safe; the symmetric argument covers the other case.
def max_container_area(height: list[int]) -
Find every unique triplet whose sum is zero by combining sorting, a fixed value, and an inward two-pointer scan.
Given an integer array nums, return all unique triplets [a, b, c] such that a + b + c = 0. The answer must not contain duplicate triplets.
Input: nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]Input: nums = [0, 0, 0, 0]
Output: [[0, 0, 0]]After sorting, fixing nums[i] turns the remaining search into a sorted two-sum problem. Pointer movement changes the sum predictably, while adjacent duplicate values can be skipped.
-nums[i].For a fixed first value, the two-pointer scan explores every feasible pair: a sum that is too small requires a larger left value, and a sum that is too large requires a smaller right value. Sorting and duplicate skipping remove repeated representations without removing any distinct triplet.
def three_sum(nums: list[int]) -> list[list[int]]:
nums
After sorting the sample to [-4, -1, -1, 0, 1, 2], fixing -1 lets the pointers find (-1, 2) and (0, 1). The next fixed -1 is skipped, so those triplets are not repeated.
Partition an array containing only 0, 1, and 2 in one pass with three boundaries and constant extra space.
Given an array nums containing only 0, 1, and 2, sort it in place so equal values are adjacent and appear in the order 0, 1, 2. Do not call a library sorting function.
Input: nums = [2, 0, 2, 1, 1, 0]
Output: [0, 0, 1, 1, 2, 2]Input: nums = [2, 0, 1]
Output: [0, 1, 2]nums[i] is 0, 1, or 2.Maintain four regions: confirmed 0s, confirmed 1s, unknown values, and confirmed 2s. The middle pointer classifies one unknown value at a time.
low and mid to 0, and high to the final index.nums[mid] is 0, swap it with nums[low] and advance both pointers.mid.nums[high] and decrease high; do not advance mid yet.The maintained regions are [0, low) for 0s, [low, mid) for 1s, and (high, n) for 2s. Each operation places one value into its final region and shrinks the unknown interval. When mid > high, no unknown values remain.
def sort_colors(nums: list[int]) -> None:
low = mid = 0
high = len(nums) -
Starting with [2, 0, 2, 1, 1, 0], the first 2 moves to the high region. The incoming 0 is then moved to the low region. Repeating this classification leaves the regions joined as 0s, then 1s, then 2s.
high, inspect the incoming value at mid before advancing.Find the shortest substring containing a target as a subsequence by alternating a forward match with a backward contraction.
Given strings s and t, return the shortest contiguous substring of s in which t appears as a subsequence. If several windows have the same minimum length, return the leftmost one. Return an empty string if no window exists.
Input: s = "abcdebdde", t = "bde"
Output: "bcde"Why: Both "bcde" and "bdde" contain b, d, e in order; the leftmost shortest window is returned.
Input: s = "hello", t = "world"
Output: ""s and t contain case-sensitive letters.A forward scan finds the earliest end of a window that completes the subsequence. Starting at that end, a backward scan matches t in reverse to find the latest possible start for that same end.
s while advancing a pointer through t on matches.t is matched, record the window end.t.The forward phase finds a valid end. For that end, the backward phase chooses each required character as far right as possible, so its resulting start is the latest—and therefore the window is the shortest—for that end. Restarting after this start considers every later possible start, so the best recorded window is globally shortest.
Calculate trapped water in one pass by maintaining the best boundary seen from each side.
Given nonnegative integers representing an elevation map where every bar has width 1, return how many units of rain water are trapped after rainfall.
Input: height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
Output: 6Input: height = [4, 2, 0, 3, 2, 5]
Output: 9Water above a position is limited by the lower of its best left and right boundaries. When the left boundary is no higher than the right boundary, the left side already has a sufficient opposite boundary, so its water can be finalized without knowing future interior heights.
left_max and right_max.When left_max ≤ right_max, the water at the left pointer is determined by left_max: a right boundary at least that high is known to exist. The algorithm safely finalizes that position. The symmetric rule applies to the right pointer, so every position contributes exactly its trapped water.
def trap_rain_water(height: list[int]) -> int:
left, right = 0, len(height) -
In [4, 2, 0, 3, 2, 5], the left boundary remains 4 while the pointer visits heights 2, 0, 3, and 2. Those positions contribute 2, 4, 1, and 2 units, for a total of 9.
In "A man, a plan, a canal: Panama", the pointers first compare A and a. They skip spaces and punctuation independently, and every meaningful mirrored pair matches.
For [0, 0, 1, 1, 2], the read pointer ignores the second 0, writes 1 at index 1, ignores the next 1, and writes 2 at index 2. The valid prefix becomes [0, 1, 2].
k positions are irrelevant and do not need to be erased.For [2, 7, 11, 15] and target 9, the first pair already sums to 17, so the right pointer moves left twice. The pair 2 and 7 then matches the target.
The algorithm starts at indices 0 and 8. Because height 1 is the bottleneck, it moves the left pointer. The pair at indices 1 and 8 then yields min(8, 7) × 7 = 49, the maximum.
For s = "abcdebdde" and t = "bde", the first forward pass ends at e in "abcde". Backtracking contracts the candidate to "bcde". A later pass finds "bdde", but the equal-length earlier window remains the answer.
t must appear in order.start + 1, not after the old end, or overlapping optimal windows can be missed.