trapping-rain-water

Difficulty: Hard  ·  Topic: Two Pointers  ·  Practice it on parikshan: /practice/trapping-rain-water/start

The story

The Mumbai Metropolitan Region Development Authority hires a contractor to simulate monsoon water retention on a stretch of road profile produced by a Topcon laser scanner. The road is sampled at one-metre intervals; each sample is the road's elevation in centimetres. The simulator must compute, for any given profile, the total volume of water that would be trapped between high points after a heavy rain. Each metre of profile contributes its own little puddle, and the puddle depth at column i depends on the tallest column to its left and the tallest column to its right. The scanner can produce profiles of fifty thousand samples; the simulator runs many profiles per hour. Linear time only.

That is trapping-rain-water. It is the canonical hard two-pointer problem because two pointers are not the only solution, and the path that gets you there forces you to earn the constant-space answer.

What's actually being asked

Given n non-negative integers h[0..n-1] representing an elevation map of unit-width bars, return the total volume of water that would be trapped after rain. Water above index i is max(0, min(maxLeftOf_i, maxRightOf_i) - h[i]) where maxLeftOf_i is the tallest bar in h[0..i] and maxRightOf_i is the tallest in h[i..n-1].

The naive approach

For each i, scan left for maxLeft[i] and right for maxRight[i]. O(n²). For n = 50,000 Python will not finish inside three seconds.

A first real improvement: precompute two prefix-max arrays in linear passes, then sum the per-index trapped water. O(n) time, O(n) space. Correct, easy to write. This is the answer the AI agent will write if you do not specify "constant space".

The key insight

You do not need both prefix-max arrays at the same time. At every step, you need only the running max from the side you are looking at, and you only need it for the side whose answer is fully determined right now. Which side is that? The shorter of h[l] and h[r].

Why? Suppose h[l] <= h[r]. We are guaranteed at least one bar on the right of l that is at least as tall as h[l], namely h[r] itself. Therefore the right-side max bound for index l is >= h[l], and the binding constraint for the water above l is the left running max. So:

• Update lmax = max(lmax, h[l]).
• Add lmax - h[l] to the total (always non-negative because of the previous line).
• Advance l.

Symmetric when h[r] < h[l]. The argument is iterative: at every step the shorter pointer's water is fully determined, even though we never built the right-max array for that index, because the existence of the other pointer guarantees the other-side max is at least the current value.

This is the two-pointer trick that wins. O(n) time, O(1) space, single pass.

The key insight (stack, for comparison)

An alternative gives the same time complexity but with a different mental model. Walk left to right with a stack of indices in strictly decreasing height. When you see a bar h[i] taller than the top of the stack, you have just discovered the right wall of a basin. Pop the top (call it bottom), peek at the new top (the left wall, call it left). Width is i - left - 1, height is min(h[i], h[left]) - h[bottom], area adds to the total. Repeat until the stack's top is no shorter than h[i], then push i.

The stack approach is excellent intuition. It handles the problem in clearly separated "basins" you can visualise. But it uses O(n) extra memory. For most production rainwater-style queries (load balancing, traffic shaping, fluid simulations) the constant-space two-pointer wins on cache behaviour alone.

Why two pointers wins on space: the stack stores indices proportional to the number of "staircases" in the profile, which in the worst case is O(n). Two pointers replaces that with two integers and two running maxes, four scalars total. On a hot path in a tight loop, four scalars stay in registers; an n-deep stack hits L1/L2 cache and brings allocation overhead. For the same algorithmic complexity, two pointers is the production-grade answer.

Step-by-step approach

1. If n < 3, the answer is 0; print and return.
2. Initialise l = 0, r = n - 1, lmax = 0, rmax = 0, total = 0.
3. While l < r:
   • If h[l] < h[r]:
     • lmax = max(lmax, h[l]).
     • total += lmax - h[l].
     • l += 1.
   • Else:
     • rmax = max(rmax, h[r]).
     • total += rmax - h[r].
     • r -= 1.
4. Print total.

Worked example

h = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
n = 12

Initial state: l = 0, r = 11, lmax = 0, rmax = 0, total = 0. The branch column shows which side of the if h[l] < h[r] test the iteration takes (strict <). add is the contribution to total on that iteration.

Read the lmax and rmax columns as their value after the update in that iteration. The add column equals lmax - h[l] on the h[l] < h[r] branch and rmax - h[r] on the else branch. Running total: 0 + 0 + 0 + 1 + 0 + 1 + 0 + 0 + 1 + 2 + 1 = 6. Final answer 6, matching the public test.

Counter-case h = [5, 0, 5]. Quick trace:

Final 5, as expected for one cell of depth 5 between two walls of height 5.

Complexity

• Time: O(n). Each pointer moves at most n steps.
• Space: O(1) for two pointers, O(n) for the prefix-max or stack approach.

For n = 50,000, this is microseconds in Python, well under the 3-second limit.

Common pitfalls

• Adding lmax - h[l] before updating lmax. That can produce a negative addition and corrupt the total. Update first, add second.
• Branching on h[l] <= h[r] and updating both lmax and rmax in the same iteration. The two pointers must move independently; sharing the update introduces double-counting near ties.
• Returning early when total > 0 after a step. No monotonicity in total; you must finish the loop.
• Confusing this with container-with-most-water. That problem asks for one rectangle; this problem asks for the total volume across all indices.
• Not handling n == 0 or n == 1. No water can be trapped.
• Reading the input wrong when n == 0. The input line may be blank.

Where this shows up in the enterprise

• MMRDA / Larsen & Toubro civil simulation: monsoon water trapping on a road profile, exactly as the story.
• NVIDIA CUDA memory pool fragmentation: "how much memory is trapped between live allocations" maps onto the same skeleton.
• AWS S3 storage tiering: total under-utilised "valley" capacity bracketed by hot-tier peaks.
• Bloomberg volatility regime detection: total "calm volume" trapped between two volatility spikes is a regime signal.
• Datadog request-rate analysis: sum of slack capacity in valleys between peak request bursts to forecast safe burst headroom.
• Tesla Autopilot drainage modelling: simulated rainwater on road-surface profile for hydroplaning risk.
• Adobe Photoshop content-aware fill: per-pixel "depth below local maxima" used in seam-carving heuristics.
• Spotify replay-gain levelling: total "headroom" trapped between loud peaks when normalising an album.

The pattern is "per-cell capped capacity bounded by left and right maxes, summed over all cells." Any system that computes total bounded-by-neighbours capacity reaches for this skeleton.

Variants you'll see elsewhere

• container-with-most-water: max single rectangle instead of total volume.
• trapping-rain-water-ii: 2D grid; cells leak in four directions. Needs a min-heap on the boundary, not two pointers.
• largest-rectangle-in-histogram: max rectangle whose height is the min over a range; needs a monotonic stack.
• sum-of-subarray-minimums: per-cell contribution like rainwater, but for subarray mins. Monotonic stack.
• maximum-binary-tree: stack-of-decreasing-values pattern that solves a different question with the same scaffold.

How parikshan turns this into a learning loop

After you read this article and click through to the practice link, the parikshan flow integrates four layers:

1. The editor runs your code against public tests for instant feedback and against per-session dynamic private tests (generated freshly per session). Synthetic cases include n == 0, single bars, two bars, V-shapes ([5, 0, 5] → 5), strictly monotone (zero), flat plateaus, and very long mostly-flat profiles with the occasional spike.
2. Hints are graduated. Level 1 nudges you to the per-cell formula. Level 4 hands you the full two-pointer recipe. Each level docks integrity.
3. The AI training assistant in exam mode offers Explain, Review, Find Bugs, Add Comments, Optimise, each costs integrity. In practice mode chat is free; this is the right place to ask "walk me through why the shorter side is the one we process".
4. The dispute flow runs after the verdict. The most common dispute on this problem is "my stack solution is correct but it uses O(n) memory and the harness times out". Read the spec, the time limit is for the input size, not the algorithm class.

Read this concept first, attempt the problem in practice mode with the prefix-max version, then redo it in exam mode using two pointers from memory. When you can derive the "shorter side is fully determined" argument from scratch in three minutes, the pattern is yours.

In the AI-integrated workspace

In your future job, the agent writes the code. Your job is to:

1. Recognise that "per-cell capacity bounded by left and right maxes, summed" is the rainwater pattern. The five-second recognition is the entire skill.
2. Tell the agent precisely: "two pointers, move the shorter side, update its running max before adding". Each clause is load-bearing. If you only say "rainwater problem", you will get the O(n)-space prefix-max version.
3. Read the generated code and verify three things: lmax/rmax are updated before the addition, only one pointer moves per iteration, and the loop bound is l < r (strict).
4. Push the edge cases the agent will miss: empty input, single bar, two equal bars (zero water), V-shape, and a long flat valley between two tall walls.

Candidates who can derive the two-pointer correctness argument unprompted are the ones who turn AI into leverage, they can not just write the code but review it under load and catch the off-by-one that costs production. Candidates who only know "rainwater means prefix max" end up with O(n) memory in a system that explicitly forbade it. parikshan is built to train the first kind.