Two Pointers: Practice Questions

Define what a "two-pointer" solution is, and give the argument that makes it O(n). Show a movement counter that proves the bound on real input.

There are three shapes of two-pointer solution. Name them, say what question each one answers, and give a one-line example of each.

Write the nested-loop version of "find two values summing to a target" and count its operations. State precisely what has to be true about a problem before two pointers can beat it.

On a sorted list, find two values summing exactly to a target in O(n). Prove that discarding a pointer's value is safe — do not just assert it.

Turn the elimination argument into a reusable four-line template, and apply it to a second problem to show it generalises.

Run the pair-sum two-pointer on unsorted input. Show that it does not raise, does not loop forever, and simply returns the wrong answer — then say why that is the dangerous failure mode.

Count all pairs of indices in a sorted list whose values sum to a target — including duplicates. Getting the duplicate arithmetic right is the whole question.

Count pairs whose sum is strictly less than a target, in O(n). The trick is that one comparison settles many pairs at once.

Find the pair whose sum is closest to a target — no exact match required. Show why the same elimination rule still applies when there is no hit to stop on.

Decide whether one string is a subsequence of another using two same-direction pointers. Prove that skipping a non-matching character in the haystack can never lose a match.

You must answer "is this a subsequence?" for thousands of different needles against one fixed haystack. Show why the O(n) walk is now the wrong shape, and what changes.

Find the k-th element from the end of a sequence in a single pass, without knowing the length in advance. Two pointers held a fixed distance apart is its own idiom.

Find the middle element in one pass with a fast pointer and a slow pointer. State the convention you pick for even lengths and make the code match it.

A slow pointer takes one step, a fast pointer takes two. Prove that if the walk ever enters a cycle, the two must eventually land on the same position — and that the proof needs the ratio to be exactly 2:1 to be this simple.

An array of n values in the range 0..n-1 defines a walk: from index i, go to index values[i]. Detect whether that walk ever revisits a position, in O(1) space.

The two pointers have met somewhere inside the cycle. Find where the cycle begins, and prove the two-line trick that does it.

An array of n + 1 integers, each between 1 and n, must contain a repeat. Find it without modifying the array and in O(1) extra space.

Once the pointers have met, measure the length of the cycle. Then report the tail length too, and check both against a direct count.

Floyd's is not the only O(1)-space cycle finder. Implement Brent's algorithm — the "teleporting tortoise" — and count how many times each one reads the data.

Check whether a string is a palindrome with converging pointers. Then extend it to ignore case and non-alphanumeric characters, without building a cleaned copy of the string.

Decide whether a string can be made a palindrome by deleting at most one character. There is exactly one place where the walk has to branch — find it and justify why one branch level is enough.

Write the checklist you run before choosing which pointer to move, and apply it to four problems that each answer it differently.

Give two problems where a two-pointer solution looks natural and is provably incorrect. Show the failure and name the property that is missing.

Every two-pointer loop should carry a one-line invariant in a comment. Write the invariant for three loops, then break one deliberately and show the invariant catching it.

Build the decision table for this topic: given a problem statement, which two-pointer shape does it reduce to? Include the cases where the answer is "none of them".

Find all distinct triplets summing to zero. Write the O(n^3) version first, state its cost, then reduce it to O(n^2) by fixing one value and running a two-pointer walk on the rest.

Three-sum has three separate duplicate-skipping guards. Name each one, show the exact wrong output you get when it is missing, and explain why they cannot be replaced by a single set() at the end.

Find the triplet whose sum is nearest a target. Explain why the early break that three-sum-to-zero uses is not available here.

Count the triplets whose sum is strictly less than a target. Reuse the "count many pairs at once" step and state the new complexity.

Extend the pattern to four values summing to a target. Add the two pruning tests that keep it usable, and state the complexity.

Write a k_sum that works for any k >= 2, without recursion, and say honestly what that costs you in clarity.

Two-sum on unsorted input has two good solutions. Implement both, state the trade, and say which one the problem statement chooses for you.

Given wall heights, find the two walls holding the most water. Prove that moving the shorter wall inwards can never discard the best answer.

Change the container solution to move the taller wall instead, and find an input where it gives the wrong answer. Explain the failure in terms of the proof.

When the two walls are exactly equal, which one should move? Show that moving either is safe, and that moving both is also safe — then say why you should still move only one.

Compute how much water a skyline traps, the obvious way: for each column, look left and look right. State the cost and show it growing.

Remove the quadratic factor with two precomputed running-maximum arrays. State the new time and space, and confirm both against the naive version.

Now do it with two pointers and no auxiliary arrays. The proof is the interesting part: explain why the shorter side's answer is already fully determined.

Write the rain-water two-pointer with height[lo] <= height[hi] replaced by a comparison of left_max and right_max, and decide by experiment whether it is a bug or an equivalent formulation. Then explain the result.

Two strings contain # meaning "backspace". Decide whether they are equal after applying the deletions, using O(1) extra space. Explain why the walk must go right to left.

A sorted array may contain negatives, so squaring it destroys the order. Restore sorted order in O(n) with two pointers.

Try to write the sorted-squares walk filling the output from index 0 upwards. Show what goes wrong and state the rule it teaches.

Validate that a sequence strictly rises then strictly falls, and find the longest such run inside a larger sequence. The pointers here move outwards from a candidate peak.

Find the longest palindromic substring by expanding outwards from every possible centre. Explain why there are 2n-1 centres and not n.

Count every palindromic substring, counting different positions separately. Reuse the centre expansion and show why the count comes out of the loop for free.

Reverse the order of words in a character list, in place, using only converging pointers. Handle multiple spaces, and state why the two-step method works.

Find the shortest subarray that, if sorted, would sort the whole array. Solve it with two scans that move in opposite directions, and prove each boundary is where you claim.

Solve the same problem by sorting a copy and comparing element by element. Compare the two approaches on correctness, cost and clarity, and say which you would ship.

Two lists of disjoint, sorted intervals. Produce every overlap between them with a same-direction walk, and prove that advancing the list with the smaller end point is safe.

Build a classifier: given a problem statement in words, decide which of the six shapes applies, or that none does. Test it on fifteen statements and report where it is uncertain.

An array where only five distinct values appear, repeated thousands of times. Count distinct value-triplets summing to zero, and show that the guarded walk is already fast — then show the counting version that ignores the walk entirely.

A matrix whose rows are sorted left to right and whose columns are sorted top to bottom. Find a value in O(rows + cols) with two pointers, and prove that each step eliminates a whole row or a whole column.

Try the staircase walk from each of the four corners. Show that two of them work and two are stuck, and state the property that separates them.

Count pairs whose values differ by exactly k. Both pointers move in the same direction here — explain why converging pointers is the wrong shape for a difference.

People must be carried two at a time, and no boat may exceed a weight limit. A rule is proposed: repeatedly pair the heaviest with the lightest that fits. Test that rule exhaustively on small inputs rather than trusting it.

Array A has room at the end for all of array B. Merge B into A in place. Explain precisely why the write pointer must start at the end.

Two strings share a prefix and a suffix. Trim both with converging pointers, and use the result to answer "do these differ by exactly one contiguous edit?"

Find the values present in all three sorted arrays with a single pass. Show that the rule "advance whichever pointer holds the smallest value" is what makes it linear.

Decide whether two strings differ by exactly one insertion, deletion or replacement, in O(n) time and O(1) space. Enumerate the cases before writing the code.

Count the triples of side lengths that can form a triangle. Fix the largest side and walk the rest — and explain why fixing the largest is what makes one comparison enough.

Given two sorted arrays, find the pair — one value from each — whose difference is smallest. Both pointers move forwards; say which one and why.

Assign resources of given capacities to requests of given sizes, one each, maximising the number of requests served. Implement the walk, then verify the rule against an exhaustive optimum.

Two sorted arrays. Find the pair, one from each, whose sum is closest to a target. State the movement rule and prove it, then handle the case where several pairs tie.

Reverse only the characters that satisfy a predicate, leaving everything else in place. Show the skipping walk and the invariant that keeps it linear.

Apply f(x) = A*x*x + B*x + C to every value of a sorted array and return the results in sorted order, in O(n). The shape of the parabola is what makes it possible.

Given a string and a dictionary, find the longest dictionary word obtainable by deleting characters from the string. Use the subsequence walk, then measure how much a precomputed index helps.

Count the subsequences whose smallest plus largest element is at most a target. The walk counts an exponential number of subsequences without enumerating any of them.

Count ordered index triples summing to a target, where equal values at different positions count separately. Get the three duplicate cases right, and prove each formula.

Several problems in this topic begin with sorted(values). Measure when that sort is the whole cost, and find the input sizes where an O(n) hash-based solution wins outright.

Build the full decision procedure for this topic: four questions that route a problem to two pointers, to a different technique, or to brute force. Run it on ten problems and show its reasoning.

A function sorts its input, walks it, and returns indices. It passes every test. Find the bug, and write the test that would have caught it.

Three-sum's duplicate skip can be placed before recording a triplet or after. One placement is correct. Determine which by experiment and explain the difference.

Write three two-pointer loops that hang, each for a different reason. Add the one assertion that catches all three, and measure what it costs.

while lo < hi and while lo <= hi are not interchangeable. Give a problem that needs each, show the failure when they are swapped, and state the rule.

The "same index twice" bug appears in more places than the loop bound. Find three of them and write the single check that detects all three.

values[lo] + values[hi] cannot overflow in Python. Show exactly where it would in C or Java, simulate the wrap, and say what a correct implementation looks like in those languages.

Four implementations of "the largest area between two walls" — the same loop with a different move rule. Decide which ones are correct without reading the code, then explain every failure, and every apparent success.

Construct a problem where the two-pointer code is well formed, terminates, and is wrong on most inputs — because the elimination step assumes something the data does not provide. Then find the smallest counter-example automatically.

Replace the fast pointer's two-step with a three-step in cycle detection. Determine experimentally when it still works and when it does not, then explain the arithmetic.

"Find the duplicate number" with Floyd's algorithm relies on three preconditions. Break each one and show a different failure — a crash, a wrong answer and an infinite loop.

A two-pointer loop that modifies the sequence it is walking. Show three distinct ways it goes wrong, and give the two safe patterns.

Centre expansion has an off-by-one that only shows on even-length answers. Produce it, then write the property test that would have caught it on the first run.

A palindrome checker walks a string by index. Show three kinds of text where "index" and "character the reader sees" are different things, and say what each one costs you.

Four two-pointer loops that look linear. Two of them are quadratic. Identify which by measuring, then name the operation responsible in each.

Build one test harness that would have caught every bug in this band. It must work without a reference implementation wherever possible, and it must minimise its counter-examples.

Build a tracer that records every pointer move a walk makes and renders the walk as ASCII frames, with the eliminated region shaded. Use it on three different problems.

Build a reusable fuzzer: it generates inputs, compares a candidate against a reference, shrinks any counter-example to a minimum, and reports coverage of the input space it explored.

Build a small library around centre expansion: longest palindrome, count of all palindromes, all maximal palindromes, and the check for "palindrome after one deletion". Share one expansion primitive between all four.

Build a solver that answers k-sum for any k, reports the number of inner steps it took, and refuses work it cannot finish in a stated budget. Show the step counts growing with k.

Build a duplicate detector for a large read-only sequence of ids, using the fast/slow walk. Benchmark it against a set, and report honestly which one you would ship.

Build a tool that decides whether two records are "the same thing typed slightly differently". Combine common-prefix/suffix trimming, the one-edit walk and the subsequence walk, and report which rule fired.

Render a skyline and the water it traps as ASCII, then animate the two-pointer walk filling it in. Verify the picture against the computed total.

Two sorted event logs must be reconciled: what is in both, what is only in one, and where they disagree on a value. Walk them once, and handle duplicate timestamps explicitly.

Build a benchmark harness that finds the input size at which one algorithm overtakes another, and use it on three pairs from this topic. Report the crossover, not just the winner.

Build a tool that takes a problem description plus a few structured facts and returns a recommended technique, the elimination argument to prove, and the test that should be written first. Run it on enough problems to exercise every branch.

An interviewer asks: "What is the two-pointer technique, and when does it apply?" Write the ninety-second answer, then the follow-up answers to the three questions that always come next.

You are handed a three-sum implementation that returns duplicates on some inputs. Find the bug by reasoning about the invariants first; only then confirm it with a test. Show both halves of the work.

Design a service that answers "which two of my values sum closest to X?" for many different X, over a dataset that occasionally changes. State what you would build for three different read/write mixes, and be explicit about what each one gives up.

A transcribed interview on container-with-most-water, where the interviewer refuses to accept the algorithm until the candidate proves it. Follow the exchange and note where the proof actually gets made.

The capstone. Take four problems from this topic, and for each one: implement it, state the elimination argument as executable documentation, prove it holds by exhaustive differential test, measure the complexity class from timings, and produce a report that fails loudly if any claim is unsupported.