Design Gurus Logo
Trapping Rain Water (hard)

Problem Statement

Given an array of positive integers height, where height[i] represents the height of the bar in the elevation map and each bar has width 1, return how much water it can trap after raining.

Examples

Example 1:

  • Input: height = [4, 0, 3, 0, 2]
Image
  • Expected Output: 5
  • Justification: The first and third bars form a container that traps 3 units of water. The third and fifth bars trap an additional 2 units. Therefore, the total trapped water is 5 units.

Example 2:

  • Input: height = [1, 2, 1, 2, 1]
Image
  • Expected Output: 1
  • Justification: Water is only trapped between the second and fourth bars, holding 1 unit of water.

Example 3:

  • Input: height = [3, 1, 2, 4, 0, 1, 3]
Image
  • Expected Output: 8
  • Justification: The first, and fourth bars trap 3 units of water. The fourth, and seventh bars trap an additional 5 units. The total is 8 units of trapped water.

Constraints:

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

Try it yourself

Try solving this question here:

Python3
Python3
. . . .

.....

.....

.....

Unlock this and all other premium problems.
No code editor for this lesson
This lesson focuses on concepts and theory