Back

Trapping Rain Water

hard

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.

Test Cases

Copy an input into the main harness and Run to verify
Input
height = [0,1,0,2,1,0,1,3,2,1,2,1]
Expected Output
6

Explanation: The elevation map traps 6 units of rain water.

Input
height = [4,2,0,3,2,5]
Expected Output
9

Constraints

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

Hints

Hint 1 — click to reveal

Think per column, not per puddle: water above column i is min(tallest on the left, tallest on the right) - height[i].

Hint 2 — click to reveal

Two pointers let you know the limiting side without precomputing both arrays.

Java Compiler

Powered by OneCompiler. Starter code loads automatically — edit and hit Run.