This card uses the same stack as Monotonic Stack, Next Greater Element. The heights at the indices in stack never increase from bottom to top. A taller bar pops the shorter bars above it. In Next Greater Element the pop writes a distance. Here the pop closes a valley and adds water.

When bar h at index i pops index valley_i, three bars are known. The popped bar is the floor. The bar now on top, left_i, is the nearest bar to the left that is at least as tall as the floor. The arriving bar h is the first bar to the right that is taller than the floor.

The water above the floor sits between the two walls. Its width is i - left_i - 1, because the walls themselves hold no water. Its depth is min(height[left_i], h) - height[valley_i]. The floor is subtracted because the water starts above it.

Example: height = [3, 0, 2]. Index 2 has h = 2. It pops index 1 as the floor. left_i = 0, so width = 2 - 0 - 1 = 1, and the depth is min(3, 2) - 0 = 2. The total is 2.

The board replays height = [4, 2, 0, 3, 2, 5]. The top row is height. The bottom row is stack, and each cell holds an index.

Each pop adds one horizontal layer of water. Index 3 (height 3) pops index 2 as the floor and adds 1 * (2 - 0) = 2. It then pops index 1 and adds 2 * (min(4, 3) - 2) = 2. Now stack is [0, 3], and total is 4.

Index 5 (height 5) pops index 4 and adds 1 * (3 - 2) = 1. It pops index 3 and adds 4 * (4 - 3) = 4. Then it pops index 0. The stack is empty, so the floor has no left wall. This is the step marked as the trap on the board.

The break leaves the loop before stack[-1] is read. Without it, stack[-1] on an empty list raises an error. The layers add up to 2 + 2 + 1 + 4 = 9, which is the answer.

The water above index k is min(max_left, max_right) - height[k], where max_left and max_right are the tallest bars on each side. The stack computes the same amount in horizontal layers instead of one column at a time.

Each water cell sits above exactly one floor bar and between exactly one pair of walls: the nearest taller bar on each side. The pop that removes that floor adds that cell once. No cell is added twice, because a bar is popped once.

A bar of equal height needs no special case. For height = [2, 0, 2], index 2 pops index 1 and adds 1 * (min(2, 2) - 0) = 2. Index 0 has height 2, which is not below 2, so it stays on stack.

If a floor is popped and stack is empty, nothing on the left can hold the water, so the layer is empty. For height = [1, 2] the function returns 0.

Every index is pushed once and popped at most once, so the time is O(N). stack can hold all N indices when the heights fall from left to right, so the space is O(N).

Example: for 1000 bars, the loop does at most 1000 pushes and 1000 pops.

The stack adds water one horizontal layer at a time. A pop closes one valley, and the layer is width * depth.

Trapping Rain Water (LC 42) also has a two-pointer solution with O(N) time and O(1) space. It adds water one column at a time. The water above index k is min(max_left, max_right) - height[k].

Two pointers work because the water level above a bar depends on the tallest bar on each side. If max_left < max_right, the left side sets the level, whatever lies between. So the pointer on the shorter side can move in safely.

Largest Rectangle in Histogram (LC 84) has no such rule. Its walls are the nearest lower bars, and not the tallest bars. That is why it needs the stack, and why this card is the same pattern with the stack order reversed.

Interview tip: give the two-pointer solution as the optimal one, because it uses O(1) space. Then explain the stack solution to show that you can resolve the left wall and the right wall of each valley.

Container With Most Water (LC 11) is a different problem. It picks two bars and measures the area between them, and it does not need a stack.