</> MAANG.io

Intermediate

Intermediate problems that train you to pick the right approach: sliding windows, graphs, dynamic programming and more.

0 of 182 solved 0%

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.

Four meanings of a pointer: converging range ends, last-seen index, next free write slot, and min-heap frontier leading to Trapping Rain Water II

Fun fact: Trapping Rain Water II is where the technique changes. In 1-D, the water above a cell is capped by the lower of the tallest walls to its left and right, so 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 a min-heap, which is why the same problem goes from O(n) time and O(1) space to O(mn log mn) time and O(mn) space.

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


The idea in short: decide what each pointer means and the movement rule follows. "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, because otherwise a block of identical characters costs one iteration per character and the loop is harder to reason about.

Converging on runs over "aabccabba": consume matching runs from both ends until c and a differ, leaving "cca" for 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 can return a negative length on an input like "aaaa", where the two runs consume the entire string and the answer is 0.

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 helper lists beyond the output 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 a common way to shrink the input before the expensive part.
  • 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 The run-consumption and crossing conditions are 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 and O(1) extra beyond it. A stable in-place version costs O(n^2) time.

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 the inner loops (left <= right on the left side, right >= left on the right) so the length never goes negative.
  • Consuming only one character per side when the ends match. Correct, but it makes the crossing case harder to reason about.
  • Building separate positive and negative lists first. The lanes are disjoint; write straight into the result and keep the single pass.
  • Seeding only the corners in Trapping Rain Water II. The entire border goes into the heap, because 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 later cells see too low a wall and the trapped volume comes out too small.
  • 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 can then enter the heap several times and be processed more than once.

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.

Rearrange Array Elements by Sign

Core idea: You don't need to swap anything in place. Allocate a result array and keep two write cursors: one fills the even slots 0, 2, 4, ... and the other fills the odd slots 1, 3, 5, .... Walk the input once. Each positive goes to the even cursor, each negative to the odd cursor, and the cursor steps by 2. Equal counts mean both lanes fill exactly, so the signs alternate starting positive, and a left-to-right scan keeps each sign's order.


Sign in to continue reading

The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.

Sign in to read the full lesson

Sign in to MAANG.io

Use your Google or Microsoft account — no password to remember.

Continue with Google Continue with Microsoft

Please accept the terms above to continue.