Trapping Rainwater
Practice
2.6 (5 votes)
Problem
93% Success 599 Attempts 50 Points 5s Time Limit 256MB Memory 1024 KB Max Code

Once upon a time, there was a small town located in a hilly area. The town was surrounded by several hills, and each hill had multiple walls of different heights. During the rainy season, the town would often experience heavy rainfall, which resulted in the formation of small ponds in between the walls.

The locals of the town wanted to capture the rainwater and use it for their daily needs, but they were facing difficulties in doing so. They realized that the walls' heights were preventing them from trapping enough rainwater, and they needed a solution to calculate how much rainwater could be trapped in between the walls.

One day, a group of engineers came to the town and proposed a solution to the locals. They suggested using an algorithm to calculate the amount of water that could be trapped between the walls after rainfall. The algorithm would take the height of each wall as input and return the trapped water amount as output.

The engineers explained that the algorithm would work by identifying the highest wall on the left and right of each wall and then calculating the trapped water amount based on the difference between the height of the current wall and the minimum height of the two highest walls. The trapped water amount for all walls would be summed up to get the total amount of trapped water.

The locals were amazed by the proposed solution and immediately agreed to implement it. The engineers coded the algorithm, and it worked flawlessly. Now, the town could trap a significant amount of rainwater and use it for their daily needs. The locals were grateful to the engineers and thanked them for their help in solving their problems.

 If the width of each block is 1, compute how much water can be trapped between the blocks during the rainy season. 

Input Format

The first line contains an integer n, the size of the array then the next line contains n elements in the array.

Input:

N = 6

arr[] = {3,0,0,2,0,4}

Output:10

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:20
38 votes
Tags:
AlgorithmsApprovedEasyOpenSorting
Points:30
39 votes
Tags:
ApprovedBit ManipulationData StructuresDynamic ProgrammingMediumOpenSegment Trees
Points:30
4 votes
Tags:
C++GCDMathNumber Theory