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
The problem of trapping rainwater is to find out the amount of water trapped between the blocks. We can solve this problem by using a two-pointer approach, where we maintain two arrays - left and right - representing the maximum height of blocks to the left and right of the current block. We then calculate the amount of water that can be trapped at each block as the minimum of the maximum height to its left and right minus its own height. Finally, we add up the trapped water at each block to get the total trapped water.
