Goldman Sachs Trapping Rain Water Answer: Two-Pointer Solution [Solved]

Answer: 6 units of water get trapped for the classic example height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]. The two-pointer solution finds it in linear time with constant extra space, and this post walks through every step so you can reproduce it under interview pressure. In short, the method is simple once you see the trace.

The trapping rain water answer for the classic example is 6, and the reason is simple once you see it: water sits in a valley only as high as the shorter of the two walls around it. Candidates have reported this question for Goldman Sachs software engineer interviews, including CoderPad and phone rounds, and other tech and finance firms use it as a standard test of array reasoning.

The Trapping Rain Water Answer

For height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1], the trapped water is 6 units. The water collects in three pockets: 1 unit above index 2, 1 unit above index 9, and 4 units across indices 4, 5, and 6. The bar of height 3 at index 7 holds the middle pocket, and the bar of height 2 at index 10 holds the right pocket. No water stays on the ends, because water at an edge always runs off.

The Problem, Restated Simply

Start with an array of non-negative integers. Each number is the height of a bar, and every bar has width 1. Picture the bars standing side by side like a skyline. After it rains, water collects in the dips between taller bars. Your job is to compute the total amount of water trapped, measured in unit squares.

Two rules decide everything. First, a bar holds water only if a taller bar stands on both sides of it, and the shorter of the tallest bar to its left and the tallest bar to its right sets the water level at any bar. Second, water above a bar equals that level minus the bar height, floored at zero.

Why Water Gets Trapped: The One Insight

In practice, take a single bar and ask one question: how high could water rise here before it spills? On the left side, water cannot rise above the tallest bar to the left. On the right side, it cannot rise above the tallest bar to the right. The lower of those two walls is the spill point, so the water level is the minimum of the left maximum and the right maximum.

In other words, this is the whole problem in one line: trapped water at index i equals min(max height to the left, max height to the right) minus height at i, floored at zero. Every solution is just a way of computing those two maximums efficiently. Candidates who miss this insight usually try to simulate rain falling, which goes nowhere.

Trapping Rain Water Answer: The Two-Pointer Walkthrough

The two-pointer method avoids storing left and right maximum arrays. It keeps one pointer at each end and moves the pointer on the smaller side, because the smaller side limits the water level. Next, here is the full trace for height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1].

Step	Pointer moved	Bar height	Left max	Right max	Water added	Running total
1	Left, index 0	0	0	0	0	0
2	Right, index 11	1	0	1	0	0
3	Left, index 1	1	1	1	0	0
4	Left, index 2	0	1	1	1	1
5	Right, index 10	2	1	2	0	1
6	Right, index 9	1	1	2	1	2
7	Right, index 8	2	1	2	0	2
8	Left, index 3	2	2	2	0	2
9	Left, index 4	1	2	2	1	3
10	Left, index 5	0	2	2	2	5
11	Left, index 6	1	2	2	1	6

Reading the Trace

One pattern jumps out from the trace. For example, the left pointer moves whenever the left bar is shorter than the right bar, and the right pointer moves in the opposite case. A pointer landing on a new maximum traps nothing; a pointer landing on a shorter bar adds maximum minus bar height. By the time the pointers meet, the walkthrough has counted every pocket exactly once, and the total is 6.

State the reason out loud in an interview, because it is the part interviewers probe. When the left bar is shorter than the right bar, the water level on the left side is already decided: the left maximum is the limiting wall, since the right side is at least as tall. You do not need to know the full right maximum, and the same logic holds in reverse. That is why one pass is enough.

The Code, in Plain English

First, start with left at index 0, right at the last index, both maximums at 0, and total at 0. While left is less than right, compare the two bars. If the left bar is shorter, update the left maximum if the bar is taller, otherwise add left max minus the bar height to the total, then move left one step right. If the right bar is shorter or equal, do the mirror image on the right, then move right one step left. Return the total when the pointers meet.

However, one detail matters: use a strict less-than comparison for the left move, so equal bars move the right pointer. Either choice gives the correct answer, but a fixed rule prevents an infinite loop. Also add the maximum of zero and maximum minus bar height, so a new maximum never adds negative water.

Brute Force vs Two Pointers

Method	Time	Extra space	How it works
Brute force	O(n squared)	O(1)	For each bar, scan left and right for the maximums, then apply the water formula.
Prefix and suffix arrays	O(n)	O(n)	Precompute the tallest bar to the left and right of every bar, then apply the formula in one pass.
Two pointers	O(n)	O(1)	Move the pointer on the shorter side and use the running maximum as the limiting wall.
Monotonic stack	O(n)	O(n)	Track bars in decreasing height and compute trapped water when a taller bar closes a valley.

For example, in an interview, start with brute force in one sentence, then improve it. That order proves you understand the problem before you optimize it, while jumping straight to two pointers sounds memorized.

Edge Cases That Catch Candidates

An empty array traps zero water, and so does an array with one or two bars, because a valley needs walls on both sides. A strictly increasing or strictly decreasing array traps nothing, because water runs off the low end. Similarly, an array of equal heights traps nothing, and neither does a single tall bar in flat ground, because there is no second wall.

Similarly, check your method on a second example: height = [4, 2, 0, 3, 2, 5] traps 9 units. Indices 1 through 4 contribute 2, 4, 1, and 2 units, since the left wall is 4 and the right wall is 5, so the limiting level is 4 throughout. If your code gives a different number, check whether you used the maximum instead of the minimum of the two walls, the most common bug.

Follow-Up Traps

Overall, the first follow-up is usually the snow variant, where the same array logic applies but the story changes to snow piling in valleys. Goldman Sachs interview reports mention exactly this variation, called Snow Trap. The method does not change, so say so plainly rather than starting over.

Next, the second follow-up asks what changes if the bars have different widths. Then you multiply each unit of water by the width of that bar, and the two-pointer method still works with that one adjustment. The third asks for the two-dimensional version, where a height map holds water in its dips. That version needs a priority queue and is much harder, so do not pretend the one-dimensional method extends to it.

Finally, a fourth trap is the container question, which looks similar but is different. Container With Most Water asks for the largest area between two bars, not the water trapped between many bars. If you mix the two up, your answer will be wrong even though both use two pointers.

What the Interviewer Is Testing

This question tests four things at once: turning a picture into a formula, optimizing from quadratic brute force to linear time and constant space, handling edge cases without being prompted, and explaining your reasoning as you go. In fact, a silent correct solution is weaker than a narrated one with a small fix at the end.

In short, practice by explaining the trace table out loud before you write code. If you can land on 6 without notes and explain why the smaller side moves, you have answered the real question, not just the example.

Frequently Asked Questions

What is the trapping rain water answer for the classic example?

The answer is 6 units for height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]. As a result, the two-pointer and prefix array methods both give 6, a good cross-check in an interview.

What is the time and space complexity of the two-pointer solution?

Time is linear, O(n), because the method visits each bar once. Extra space is constant, O(1), because the method stores only the two pointers, the two maximums, and the total.

Why does the two-pointer method move the smaller side?

The smaller side is the limiting wall. When the left bar is shorter than the right bar, the left maximum already decides the water level, so you can process the left bar without knowing the full right maximum.

Is trapping rain water actually asked at Goldman Sachs?

Yes, candidates have reported it in Goldman Sachs software engineer interviews, including CoderPad rounds, phone rounds, and a Snow Trap variation. Reports are candidate-shared, so treat them as evidence of the question style, not as a guarantee for any single round.

More interview puzzles in this series: 25 Horses Puzzle Answer, Goldman Sachs Clock Angle at 11:55, Goldman Sachs 5 Pirates Puzzle, and Bridge and Torch Puzzle Answer.