PIXELBANKv8.2.1
Menu

Trapping Rain Water

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:
  • We initialize two pointers, one at the start and one at the end of the elevation map, to track the maximum height of the left and right bars.
  • We compare the heights of the bars at the current positions of the two pointers and move the pointer with the smaller height towards the other end, calculating the trapped water as heightmaxheightcurrentheight_{max} - height_{current}, where heightmaxheight_{max} is the maximum height of the left or right bar.
  • At each step, we update the maximum height of the left or right bar if the current bar is higher, ensuring that we capture the maximum amount of trapped water.
  • The total trapped water is the sum of the trapped water at each position, resulting in a total of 66 units of water trapped between the bars.

Constraints:

  • 1 <= len(height) <= 2 * 10^4
  • 0 <= height[i] <= 10^5
Editor

Test Results

0/0
Run code to see test results.