Trapping Rain Water | Dataford Interview Questions

ByteDance video analytics can represent a one-dimensional terrain profile as adjacent elevation bars. Given the bar heights, compute how many units of rainwater remain trapped after rainfall.

Each bar has width 1, and water can be trapped only where taller bars form boundaries on both sides. Return the total trapped volume.

Formal Specification

Implement trap_rain_water(height), where height is a list of non-negative integers. Return an integer representing the total trapped water. The function must run in linear time and use constant auxiliary space.

Constraints

0 <= height.length <= 2 * 10^4
0 <= height[i] <= 10^5
Each bar has width 1
The result fits in a standard Python integer

Function Signature

def trap_rain_water(height):

Your question is Trapping Rain Water. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem