Trapping Rain Water

Hard · Two Pointers

You are given an array of non-negative integers representing the height of a bar at each position along a flat surface, with bars having width 1 and no gaps between them. After rain falls, water gets trapped between bars based on the height of the tallest bars to its left and right. Return the total volume of water that ends up trapped across the whole array.

Examples

Input:  height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Why:    Water pools above the lower bars wherever taller bars exist on both sides, adding up to 6 units total.

Input:  height = [4,2,0,3,2,5]
Output: 9
Why:    The tall bars at the ends (4 and 5) trap water over the dip in the middle, totaling 9 units.

Input:  height = [1,1,1]
Output: 0
Why:    All bars are the same height so no water can be held anywhere.

Constraints

1 <= height.length <= 2*10^4, 0 <= height[i] <= 10^5

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Trapping Rain Water

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Trapping Rain Water. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.