Converging and Write Pointers

What is this?

"Two pointers" suggests one arrangement: an index at each end, walking inward. This chapter is about what happens when you take the idea seriously and ask what else can an index mean? It can mean the next free slot in a particular output lane. It can mean the last place a word was seen. And in two dimensions, where the next thing to process is the lowest point on an entire perimeter, the pointer stops being an index at all and becomes a priority queue.

💡 Fun fact: Trapping Rain Water II is the moment the technique changes species. In 1-D, water above a cell is bounded by the taller of the two highest walls on either side — two pointers suffice. In 2-D there is no "either side": water escapes through the lowest point anywhere on the boundary, so the frontier must always give up its minimum first. That requirement is precisely a min-heap, which is why the same problem jumps from O(n) and O(1) space to O(mn log mn) — and why interviewers use it to see whether you understand why a pointer works, or merely that it does.

🔓 The 4 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: decide what each pointer means and the movement rule writes itself. "The ends of the unresolved range", "the next free even slot", "where I last saw this word", "the lowest unprocessed boundary cell" — four meanings, four algorithms, one habit.

1. Converging on runs

The plain converging walk compares the two ends and moves one. The refinement here is that when both ends are equal, you must consume each side's entire run before comparing again — otherwise a block of identical characters costs one iteration per character and the invariant gets muddled.

s = "aabccabba"          index:  0 1 2 3 4 5 6 7 8
                                 a a b c c a b b a

left=0 'a', right=8 'a'   → match
   consume left run  "aa" → left = 2
   consume right run "a"  → right = 7

left=2 'b', right=7 'b'   → match
   consume left run  "b"  → left = 3
   consume right run "bb" → right = 5

left=3 'c', right=5 'a'   → differ → stop
   remaining = indices 3..5 = "cca"  → answer 3

Note the runs are different lengths on each side — two as on the left, one on the right — which is exactly why each side consumes its own run independently rather than stepping in lockstep.

The stopping condition is the subtle part: you stop when the two ends differ, or when the pointers meet or cross. Getting the crossing case wrong returns a negative length on an input like "aaaa", where the two runs consume the entire string.

2. Last-seen pointers

Not every pointer moves through the data. Sometimes the useful state is where I last saw a thing: walk once, and whenever you encounter one of the two words of interest, update its remembered position and compare against the other's. One pass, two integers, no nested loop.

3. Write lanes

One read pointer, several write pointers — each owning a category of output position. Reading sequentially and dropping each element into its lane's next free slot produces a stable interleaving in one pass with no extra array. The lanes never collide because their positions are disjoint by construction (even indices versus odd indices, say).

4. The heap as a pointer

When the frontier is a perimeter rather than two endpoints, "which one moves next" is a global minimum question. A min-heap answers it in O(log n), and the algorithm is otherwise unchanged: pop the lowest boundary cell, process its unvisited neighbours, push them onto the frontier with the water level carried forward.

5. Where you'll actually meet this

• Terrain and flood modelling. Given an elevation raster, how much water is retained after rain? The heap-based inward flood is the standard GIS answer, not an interview invention.
• Stream compaction on GPUs. Partitioning elements into lanes by category, in place and in one pass, is a primitive that CUDA and shader pipelines provide directly.
• Text diffing and trimming. Peeling matching prefixes and suffixes before running an expensive diff is how real diff tools cut the problem down first.
• Log analysis. "Closest occurrence of event A to event B" over a long event stream is the last-seen pointer, and it is why the naive nested scan is never needed.
• Image processing. Watershed segmentation floods a heightmap from its minima using the same priority-queue frontier.

6. Problems in this chapter

▶ Minimum Length of String After Deleting Similar Ends

Repeatedly strip matching prefix and suffix runs. The pure converging walk — with the run-consumption and crossing conditions being the whole difficulty.
Pattern: converge on runs. Target: O(n) time, O(1) space.

▶ Shortest Word Distance

Minimum index gap between two words in a list. Track each word's last-seen position; every time one updates, the gap to the other's stored position is a candidate.
Pattern: last-seen pointers. Target: O(n) time, O(1) space.

▶ Rearrange Array Elements by Sign

Alternate positives and negatives while preserving relative order within each sign. Two write lanes — even slots and odd slots — fed by a single read pass.
Pattern: write lanes. Target: O(n) time, O(n) for the output (or O(1) extra if allowed to build in place).

▶ Trapping Rain Water II

Water retained on a 2-D elevation grid. Seed a min-heap with the border, repeatedly pop the lowest boundary cell, and flood inward — trapping boundary − height at every lower neighbour and pushing it back with the raised level.
Pattern: min-heap frontier. Target: O(mn log mn) time, O(mn) space.

7. Common pitfalls 🚫

• Stopping one step late when converging. After consuming runs the pointers can cross; guard with left <= right and clamp the resulting length at zero.
• Consuming only one character per side when the ends match. Correct, but it obscures the invariant and makes the crossing case harder to reason about.
• Rebuilding the answer array in the write-lane problem. The lanes are disjoint; write directly and keep the single pass.
• Seeding only the corners in Trapping Rain Water II. The entire border goes into the heap — every edge cell is a potential escape route.
• Forgetting to raise the water level. When you flood into a lower neighbour, it enters the frontier at the boundary's height, not its own; otherwise water leaks downhill.
• Using a max-heap out of habit. The escape route is the lowest wall, so it must be a min-heap.
• Marking cells visited on pop instead of on push in the heap flood — the same cell then enters the heap several times and the water accounting double-counts.

8. Key takeaways

1. Name the pointer's meaning first. Every movement rule in this chapter follows mechanically from what the index is defined to represent.
2. Consume whole runs when both ends match — one decision per run, not per element.
3. A pointer need not move. "Where I last saw X" is state, and it solves closest-occurrence problems in one pass.
4. Disjoint write lanes turn interleaving and partitioning into a single sequential pass.
5. In 2-D, the pointer is a min-heap. When the next thing to process is a global minimum over a frontier, the priority queue is the index.
6. Why interviewers love it: the 1-D version is memorisable, the 2-D version is not. Being asked to extend the idea is a direct test of whether you understood the invariant or the syntax.

Order: Minimum Length of String After Deleting Similar Ends → Shortest Word Distance → Rearrange Array Elements by Sign → Trapping Rain Water II.