Rain Water Trapping Problem
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining?
Input:
The first line of input contains an integer T denoting the number of test cases. The first line of each test case is N, N is the size of the array. The second line of each test case contains N input arr[i], where arr[i] represent the height of the building.
Output:
For each testcase, print the maximum water stored in those building.
Examples:
Input:
T = 1
N = 6
[6,2,4,2,4,6]
Output:
12, 4, units of water at index 1 and 3 and 2 unit
of water at index 2 and 4, hence overall 12 units of water.
Input:
T = 1
N = 3
[4,4,4,4,4]
Output:
0,
We cannot store any amount of water in
this construction as all are equal.
1) Brute Force Approach
The idea is to traverse every array element and find the highest bars on the left and right sides. Take the smaller of two heights. The difference between the smaller height and height of the current element is the amount of water that can be stored in this array element.
We will traverse the array from start to end, for every element we will find the maximum value from left and right and then take the minimum value and subtract that from the current height of the building. We will keep summing the values from first to last.
Pseudo Code:
C++ Implementation:
Output
2) Efficient Approach
We will use precomputed values of height in two arrays left and right.
Initially left[0] value will be same as left[0]=arr[0] as there are no other element left of it and right[n-1] will be arr[n-1] as there is no other right element. For other elements we will take min(left[i],right[i])-arr[i] as the sum of water.
Pseudo Code:
C++ Implementation:
Output