v9.1.1
Menu

Trapping Rain Water

hardFREEArrays & SortingAmazon DSA

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.

Example

Input
0,1,0,2,1,0,1,3,2,1,2,1
Output
6
Reasoning
  • The input is a list of 1212 bar heights, h0,…,h11h_0, \dots, h_{11} = 0,1,0,2,1,0,1,3,2,1,2,1, each 11 unit wide. The output is the total units of water trapped.
  • Water above column ii is capped by LiL_i, the tallest bar at or left of ii, and RiR_i, the tallest at or right of ii. The lower one sets the level, so column ii holds min⁡(Li,Ri)−hi\min(L_i, R_i) - h_i units.
  • Column 22 (h=0h=0): tallest left is 11, tallest right is 33, level 11, so it holds 11.
  • Columns 4,5,64, 5, 6 (heights 1,0,11, 0, 1) sit between the 22 at index 33 and the 33 at index 77, so the level is 22: they hold 1+2+1=41 + 2 + 1 = 4.
  • Column 99 (h=1h=1) sits between two bars of height 22, so it holds 11. All other columns hold 00.
  • Total: 1+4+1=61 + 4 + 1 = 6. Notice the edges can never hold water: column 00 has nothing to its left, and the final 11 has nothing to its right.

Constraints

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

More from Amazon DSA

solution.py

Test results

Sign in to run your code against the test cases.