Cascadiq

Trapping Rain Water

algorithm · Level 3 · 35 min

Description

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Imagine rain falling on the bars; water is trapped between bars when there are higher bars on both sides.

Requirements

  • Implement a function that takes height (array of non-negative integers).
  • Return the total amount of rain water that can be trapped.

Constraints

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

Deliverables

Return the total trapped water (integer).

Tags

ArrayTwo PointersStackDynamic Programming