Trapping Rain Water

Try to solve the Trapping Rain Water problem.

We'll cover the following

Statement#

Given a sequence of non-negative integers representing the heights of bars in an elevation map, the goal is to determine the amount of rainwater that can be trapped between the bars after rain.

Constraints:

  • n==n == heights.length

  • 0≤0 \leq heights[i] ≤105\leq 10^5

  • 1≤n≤1031 \leq n \leq 10^3

Examples#

canvasAnimation-image

1 of 2

canvasAnimation-image

2 of 2

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Trapping Rain Water

1

What is the maximum amount of water that would be trapped for the following given input?

heights = [0, 1, 2, 0, 1, 3]

A)

7

B)

3

C)

6

D)

5

Question 1 of 30 attempted

Figure it out!#

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Drag and drop the cards to rearrange them in the correct sequence.

Initialize two pointers, left and right to iterate the given heights array.

Iterate the array and at each iteration, based on the lower maximum height among the two sides, start computing the amount of rain water that can be trapped.

For each bar in the heights array, find the difference between the maximum height of that side and the current bar’s height.

Add this amount to the stored_water variable and update the maximum of the respective side to ensure the correct calculations for the subsequent iterations.

Repeat this process until left becomes greater than right. Return the cumulative sum stored in the stored_water variable.

Try it yourself#

Implement your solution in the following coding playground.

Python
usercode > main.py
Input #1
%0 node_01 1 node_11 0 node_21 3 node_31 0 node_41 1 node_51 2
Visualization for Input #1
Trapping Rain Water

Solution: Sum of Three Values

Solution: Trapping Rain Water