Two Pointers Problems

Six classic interview problems — Valid Palindrome, Two Sum II on a sorted list, 3Sum, Container With Most Water, Trapping Rain Water and Remove Duplicates in place — solved from zero with one idea: keep two positions in the list and move them by a rule. For each problem you will see the slow obvious idea, the reason each pointer move is safe, the pseudocode, the Dart code, and an animation you can feed your own input. By the end you will know when two pointers apply, why they never miss the answer, and when sorting first is worth its cost.

What "two pointers" means and why it works

Some words first:

• A pointer here is just a whole number that holds a position (an index) in a list. "Move the pointer right" means "add 1 to that number". It is not the memory-address kind of pointer from languages like C. Lists and indexes are covered in D26 · List methods.
• Opposite ends: one pointer left starts at index 0, the other right at the last index, and they move toward each other until they meet. Used by Valid Palindrome, Two Sum II, 3Sum, Container With Most Water and Trapping Rain Water.
• Slow and fast (also called reader and writer): both start at the left and move the same way. fast reads every item; slow only moves when something is worth keeping and marks where the next kept item is written. Used by Remove Duplicates, Move Zeroes, and (with "one step versus two steps") by loop detection in a linked list.
• O(n) ("order n") means the work grows in step with the input size n. O(n²) means twice the input gives four times the work. O(1) extra space means only a few variables, however big the input. See C03 · Growth of Functions.

Why a pointer move never loses the answer

The brute force for a pair problem tries every pair (i, j) with i < j: n(n − 1)/2 of them. Picture them as a triangle-shaped grid: row i, column j, and in each box the sum nums[i] + nums[j]. When the list is sorted, the sums in that grid grow as you go right along a row and grow as you go down a column.

The two pointers always test the top-right box that is still alive, (left, right). Then:

• Sum too small. nums[right] is the biggest partner nums[left] still has. If even that is too small, every box in row left is too small. The whole row is thrown away with one test: left moves right.
• Sum too big. nums[left] is the smallest partner nums[right] still has. If even that is too big, the whole column right is too big: right moves left.

Each test removes a full row or a full column, and nothing removed could have been the answer. That is the whole proof idea, and every opposite-ends problem on this page has the same shape: "the item I move away from can never be part of a better answer than the ones I have already checked." Since there are only n − 1 rows and columns to remove, the loop does at most n − 1 tests: O(n) instead of O(n²). Watch the grid shrink:

When is sorting first worth O(n log n)?

The proof above needs order: "nums[right] is the biggest partner left" is only true in a sorted list. If the list is not sorted, you can sort it first. Sorting n items costs O(n log n) — for n = 10⁵ that is about 1.7·10⁶ steps, tiny next to the 5·10⁹ pair checks of the brute force. How sorting works is in C02 · Insertion & Merge Sort and C07 · Quicksort.

Valid Palindrome

The task. A palindrome reads the same forwards and backwards, like "level". You get a piece of text s that may contain spaces, punctuation, capital letters and digits. Ignore everything that is not a letter (a–z, A–Z) or a digit (0–9), treat capital and small letters as equal, and answer true if what is left is a palindrome, otherwise false. Text with no letters or digits at all counts as a palindrome (nothing reads the same both ways).

Brute force. Build a cleaned, lower-case copy, build its reverse, and compare the two. That is O(n) time but O(n) extra memory for the two copies. Correct, and a fine first answer.

Key insight. A palindrome check only ever compares character k from the front with character k from the back. Two pointers can make exactly those comparisons directly on the original text, skipping the characters that do not count — no copy needed.

Why each move is safe. Skipping a space or symbol is safe because the rules say it does not count. When two real characters match, they are a finished pair: no later comparison involves them, so both pointers may move in. When they differ, the answer is decided — a palindrome needs them equal.

Optimal approach. left at 0, right at the end. While left < right: skip a non-letter/digit on either side; otherwise compare the two in lower case and either stop with false or move both inward. If the pointers meet, answer true.

An edge case: text made only of symbols. Neither pointer ever finds a real character, so the loop just skips until the pointers meet.

Complexity. Time O(n) — every step moves at least one pointer one place inward, and they meet after at most n steps. Space O(1) — two whole numbers, no copy of the text.

Follow-ups interviewers ask.

• You may delete at most one character. When the first mismatch appears, try skipping the left one or the right one and check the rest plainly: still O(n). In the bank below.
• Full Unicode text ("Ésope reste ici et se repose"). Walk over runes (whole characters) instead of code units, and use a proper letter test; string internals are in D24 · String methods.
• Longest palindrome inside a text. Two pointers again, but moving outward from each centre — question p02-q25 in the bank.

The idea underneath: strings are lists of character codes, read by index — see D04 · Strings and D24 · String methods (codeUnitAt).

Two Sum II on a sorted list

The task. You get a list of whole numbers nums that is already sorted from smallest to largest (repeats allowed), and a whole number target. Find two different positions i < j with nums[i] + nums[j] = target and return [i, j] (positions counted from 0). If no pair works, return an empty list. If several pairs work, any one is accepted; this version returns the first one the pointers meet. Use only O(1) extra memory.

Brute force. Try every pair (the panel in the first section): O(n²) time, O(1) space. It ignores the fact that the list is sorted.

Compare with Step 13.1. The map version of Step 13.1 · Two Sum works on any list in O(n) time, but stores up to n numbers in a Map: O(n) extra space. When the list is sorted, two pointers give the same O(n) time with O(1) space. When the list is not sorted and the original positions are wanted, the map wins, because sorting would scramble the positions.

Key insight and why each move is safe. Look at the current pair (left, right). If the sum is too small, then nums[left] plus any value still in range is at most nums[left] + nums[right], still too small — so nums[left] can never be in the answer and left moves right. If the sum is too big, nums[right] plus any value still in range is at least the current sum, still too big — so right moves left. Values that were thrown away can never come back into the answer, so nothing is missed.

An edge case with no answer: the pointers keep throwing values away until they meet, and the result is an empty list.

Complexity. Time O(n) — every test moves one pointer one step inward, so at most n − 1 tests. Space O(1) — two indexes and a sum.

Follow-ups interviewers ask. Count all pairs whose sum is at most a limit (when a pair fits, every partner between the pointers fits too: add right − left at once). Count pairs whose sum lies in a range (two such counts subtracted, question p02-q31). Find the pair whose sum is closest to the target (keep the best while the pointers move).

The ideas underneath: sorting (C02 · Insertion & Merge Sort) and the hash-map alternative (Step 13.1 · Two Sum, C11 · Hash Tables).

3Sum

The task. Given a list of whole numbers, return every triplet of values [a, b, c] taken from three different positions with a + b + c = 0. Each triplet is written smallest value first, and the same set of three values must appear only once in the answer, even if the list holds it several times. This version lists the triplets in increasing order of a, then b.

Brute force. Three nested loops over all triples, sort each triplet and put it in a Set to drop repeats: O(n³) time.

Key insight. Fix the first number nums[i]. Then you need two numbers to its right whose sum is −nums[i] — that is Two Sum II on the rest of a sorted list, O(n). Doing it for every i gives O(n²). Sorting first costs only O(n log n), which is smaller than O(n²), so it is free here.

Why each move is safe. Inside one fixed i the moves are the Two Sum II moves, with the same proof. The duplicate skipping is safe too: in a sorted list equal values sit side by side. If nums[i] equals nums[i − 1], every triplet starting with that value was already found in the previous round, so skipping cannot lose a new one. After a triplet is found, moving left past copies of the same middle value stops the same triplet from being added again.

The edge case where every number is the same: the triplet is found once, and the repeated first numbers are skipped.

Complexity. Time O(n²) — sorting is O(n log n), then for each of the n choices of i the two pointers make at most n steps. Space O(n) for the sorted copy (O(1) extra if you may sort the caller's list in place), not counting the answer.

Follow-ups interviewers ask. The sum closest to a target (keep the best sum while the pointers move — p02-q14). Count triplets with sum smaller than a target (p02-q23). 4Sum: fix two numbers, then two pointers, O(n³) (p02-q20). Can 3Sum be done in O(n)? Nobody knows a way much faster than O(n²) (p02-q30).

The ideas underneath: sorting (C07 · Quicksort) and the pair search of Two Sum II above. The unsorted-list pair search with a map is in Step 13.1 · Two Sum.

Container With Most Water

The task. height[i] is the height of a thin vertical wall standing at position i. Pick two walls; together with the floor they make a container. It holds min(height[i], height[j]) × (j − i) units of water: the water level is set by the shorter wall, and the width is the distance between them. The walls in between do not get in the way. Return the most water any pair of walls can hold.

Brute force. Measure every pair of walls: O(n²) time, O(1) space.

Key insight — why moving the shorter wall is safe. Start with the widest container, walls left = 0 and right = n − 1. Suppose height[left] < height[right]. Every other container that uses wall left pairs it with some wall between the two pointers. That container is narrower, and its water level is at most height[left] (the level can never be above the shorter wall). Narrower and no taller means no more water than what we just measured. So wall left has nothing better to offer, and we can drop it for good: left moves right. Moving the taller wall instead would be a mistake — the level would stay capped by the short wall while the width shrinks, and the best pair might be skipped.

Optimal approach. Measure the current pair, keep the best, move the shorter wall inward (on a tie, either one; this version moves right), and repeat until the pointers meet.

An edge case: every wall has the same height. Every move is a tie, and the widest pair turns out to be the best.

Complexity. Time O(n) — one wall is dropped per step, so n − 1 steps. Space O(1).

Follow-ups interviewers ask. Prove that the tie case is safe (with equal heights, both walls are "the shorter one", so either may go). Return the two positions, not just the area (remember them when best improves). What if walls have thickness and block water? Then it becomes Trapping Rain Water, the next problem.

The idea underneath: a greedy choice that is proved safe by an "exchange" argument — the same style of proof as in C16 · Greedy Algorithms.

Trapping Rain Water

The task. height[i] is the height of a bar of width 1 at position i, side by side like a city skyline. After heavy rain, water collects in the dips between bars. Return how many units of water are trapped in total. The water above bar i rises to the lower of "the tallest bar on its left (including itself)" and "the tallest bar on its right (including itself)", so bar i holds min(tallest left, tallest right) − height[i].

Brute force. For each bar, scan left for the tallest bar and scan right for the tallest bar, then add min − height[i]: O(n²) time, O(1) space.

Better: prefix-max arrays. The brute force repeats the same scans. Precompute leftMax[i] (tallest bar in height[0..i]) in one left-to-right pass and rightMax[i] (tallest in height[i..n−1]) in one right-to-left pass; then each bar's water is one subtraction. O(n) time, but two extra lists: O(n) space.

Key insight for O(1) space. Each bar only needs the smaller of its two maxima. Walk two pointers inward, keeping leftMax and rightMax for the parts already passed. One fact makes it work: the bar at the pointer that is not moving is always the tallest bar seen so far on either side. So if height[left] < height[right], the right side certainly has a wall at least as tall as leftMax, and the water above left is exactly leftMax − height[left] — the true right maximum can be even taller, but it no longer matters, because the lower wall decides. The mirror image holds for the right side.

Why each move is safe. We only settle a bar when we know which of its two walls is the lower one, and we know that lower wall's exact height. So every bar's water is final when the pointer leaves it, and nothing is ever recounted.

An edge case: a rising staircase. Every bar is a new tallest bar, so no water is ever poured.

Complexity. Two-pointer version: time O(n) (one step per bar), space O(1) (four numbers). Prefix-max version: time O(n) (three passes), space O(n) (two lists). The prefix version is easier to explain and to get right; the two-pointer version is what interviewers ask for when they say "constant extra space".

Follow-ups interviewers ask. Solve it with a stack (pour water layer by layer whenever a taller bar closes a dip). Rain water on a 2-D height map (a priority queue that always grows from the lowest border cell). Return how much water each bar holds, not just the total.

The ideas underneath: prefix maxima are precomputed answers to repeated questions, the same spirit as C15 · Dynamic Programming; the prefix-product trick is in Step 13.1 · Product of Array Except Self.

Remove Duplicates in place (slow and fast pointers)

The task. You get a list of whole numbers sorted from smallest to largest. Rearrange it in place (no second list) so that each different value appears once at the front, in the original order, and return how many different values there are, k. Whatever is left in the boxes after position k − 1 does not matter.

Brute force. Each time a value equals the one before it, delete it with removeAt, which shifts everything after it one place left: up to O(n²) time. Or copy the unique values to a new list: O(n) time but O(n) extra space, which the task forbids.

Key insight. In a sorted list, repeats sit side by side, so "is this a new value?" only needs a comparison with the last value kept. The kept values form a growing block at the front, and the place to write the next kept value is just after that block. Two pointers moving the same way do exactly this.

Why each move is safe. fast is always ahead of or level with slow, so writing into nums[slow] only ever overwrites a box that fast has already read — no unread value is destroyed. And because the list is sorted, a value equal to nums[slow] is a repeat of something already kept, so skipping it loses nothing.

An edge case: every value is the same, so nothing is ever written and the answer is 1.

Complexity. Time O(n) — fast visits each box once. Space O(1) — two indexes.

Follow-ups interviewers ask. Move every 0 to the end while keeping the order of the others (Move Zeroes, p02-q5). Remove every copy of a given value (p02-q9). Keep at most two copies of each value (p02-q17). Detect a loop in a linked list: the same "slow and fast" idea, but fast moves two steps for every one step of slow (p02-q21) — linked lists are built in C10 · Elementary Data Structures.

The ideas underneath: in-place list updates and why removeAt is O(n) — D26 · List methods.

Quiz

Interview questions

Variations and follow-ups of the six problems above — the questions interviewers move to once you have solved the classic version. Every solution is tested in Dart on its examples and on hundreds of random inputs against a slow reference.

Cheat sheet

Use two pointers when the input is sorted (or sorting is affordable) and a rule tells you which end is useless; use a hash map instead when the original positions matter and the list is unsorted (see Step 13.1 · Arrays & Hashing).