DSA interview question

Trapping Rain Water

Hard · Data structures · Topics: array, two pointer, stack

The problem

A city planner models a street of buildings as bar heights and asks how much rainwater would collect between them after a storm. Water above position i rises to the lower of the tallest wall on its left and the tallest wall on its right, minus the bar's own height. Precomputing left and right maximums works in O(n) extra space. The two-pointer version gets O(1) space: always move the side with the lower current wall, because that side's water level is already fully determined by its own running maximum.

Example: [0,1,0,2,1,0,1,3,2,1,2,1] → 6.

Function signature

long long trap(const vector<int>& height);

Test cases

Input	Output	Explanation
`[0,1,0,2,1,0,1,3,2,1,2,1]`	`6`
`[4,2,0,3,2,5]`	`9`
`[3,0,2,0,4]`	`7`	3 + 1 + 3
`[1,2,3]`	`0`	Rising: nothing is held
`[2,0,2]`	`2`
`[5]`	`0`

(Confirm: heights are non-negative; bars have width 1; water spilling past either end is lost.)

How interviewers phrase it

"Given n non-negative integers representing an elevation map where each bar has width 1, compute how much water it can trap after raining" (LeetCode 42).

Clarifying questions to ask

Are the edges open (water spills off)? (Yes.)
Is each bar width 1?
How large can the answer be? (It can approach 2·10⁹, so use 64-bit.)

Follow-ups to expect

"What's the per-position formula?"
"How do prefix and suffix maximums help?"
"Why can two pointers skip one of the maximums?"
"Stack solution?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview