Trapping Rain Water
You have been given a long type array/list 'ARR' of size 'N'. It represents an elevation map wherein 'ARR[i]' denotes the elevation of the 'ith' bar. Print the total amount of rainwater that can be trapped in these elevations.

Note :

The width of each bar is the same and is equal to 1.

Input format :

The first line contains an integer 'T' which denotes the number of test cases. Then the test cases follow. The first line of each test case contains an integer 'N' representing the size of the array/list. The second line contains 'N' single space-separated integers representing the elevation of the bars.

Output Format :

For each test case, print in a single line a single integer denoting the total water that can be trapped. The output of each test case will be printed in a separate line.

Note :

You don't need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1

Question

Trapping Rain Water

You have been given a long type array/list 'ARR' of size 'N'. It represents an elevation map wherein 'ARR[i]' denotes the elevation of the 'ith' bar. Print the total amount of rainwater that can be trapped in these elevations.

Note :

The width of each bar is the same and is equal to 1.

Input format :

The first line contains an integer 'T' which denotes the number of test cases. Then the test cases follow.

The first line of each test case contains an integer 'N' representing the size of the array/list.

The second line contains 'N' single space-separated integers representing the elevation of the bars.

Output Format :

For each test case, print in a single line a single integer denoting the total water that can be trapped.

The output of each test case will be printed in a separate line.

Note :

You don't need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
0 <= N <= 10^4
0 <= ARR[i] <= 10^9

Time Limit : 1 sec

Accepted Answer

The question asks to find the total amount of rainwater that can be trapped in the given elevation map.

Iterate through the array and find the maximum height on the left and right side of each bar.
Calculate the amount of water that can be trapped on each bar by subtracting its height from the minimum of the maximum heights on both sides.
Sum up the amount of water trapped on each bar to get the total amount of rainwater trapped.

Accepted Answer

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.

Accepted Answer

Brute Force Approach

The idea here is to travel over every elevation on the map and calculate the units of water the elevation can store.

Here is the algorithm :

Iterate over every elevation or element and find the maximum elevation on to the left and right of it. Say, the maximum elevation on to the left of the current elevation or element that we are looking at is ‘maxLeftHeight’ and the maximum elevation on to the right of it is ‘maxRightHeight’.
Take the minimum of ‘maxLeftHeight’ and ‘maxRightHeight’ and subtract it from the current elevation or element. This will be the units of water that can be stored at this elevation.
Compute units of water that every elevation can store and sum them up to return the total units of water that can be stored.

Space Complexity: O(1)Explanation:

O(1)

We are not using any extra space. Hence, the overall space complexity will be O(1).

Time Complexity: O(n^2)Explanation:

O(N^2), Where ‘N’ is the total number of elevations in the map.

For every elevation we make ('N' - 1) operations to find the maximum height at the left and right. Hence, the overall space complexity will be O(N^2).

Accepted Answer

Left And Right Array Approach

The idea here is to pre-compute the maximum elevation on the left and right for every element in a most optimized way.

Here is the algorithm :

Create two lists or arrays, say, ‘leftMax’ and ‘rightMax’.
At every index in the ‘leftMax’ array store the information of the ‘leftMaxHeight’ for every elevation in the map.
Similarly, at every index in the ‘rightMax’ array store the information of the ‘rightMaxHeight' for every elevation in the map.
Iterate over the elevation map and find the units of water that can be stored at this location by getting the left max height and right max height from the initial arrays that we created.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the total number of elevations in the map.

We are creating ‘leftMax’ and ‘rightMax’ arrays will take up ‘2N’ space. Hence, the overall time complexity will be O(N).

Time Complexity: O(n)Explanation:

O(N), Where ‘N’ is the total number of elevations in the map.

We take ‘3N’ operations in total. ‘2N’ operations to find the ‘leftMax’ and ‘rightMax’ arrays. Another ‘N’ operations to find the total units of water that can be stored. Hence, the overall space complexity will be O(N).

Accepted Answer

Peak Elevation Approach

The idea here is to find the maximum elevation in the array by iterating over the array once. Say, the max elevation or height is ‘PEAK’.

Taking the ‘PEAK’ as a reference point, we can say that we may store the water onto the left and right of this point.

Here is the algorithm:

Get the ‘PEAK’ value
Move from left to right in the elevation map towards the ‘PEAK’. Maintain three variables:
- ‘maxSoFar’ is the maximum elevation that has been encountered on the way towards ‘PEAK’.
- ‘countSubmerged’ which are the elevations that are smaller than the ‘maxSoFar’.
- ‘submergedArea’ which is ‘ARR[i]' * 1.
Now, every time a new ‘maxSoFar’ is reached, add ('maxSoFar' * ‘countSubmerged’ - ‘submergedArea’) to a running sum.
Repeat the same from right to left.

Space Complexity: O(1)Explanation:

O(1)

We are not using any extra space. Hence, the overall space complexity will be O(1).

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the total number of elevations in the map.

We are traversing array ‘N’ times only. Hence, the overall time complexity will be O(N).

You have been given a long type array/list 'ARR' of size 'N'. It represents an elevation map wherein 'ARR[i]' denotes the elevation of the 'ith' bar. Print the total amount of rainwater that can be trapped in these elevations.

Note :

Input format :

Output Format :

Note :

Constraints :

Top Unthinkable Solutions Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Unthinkable Solutions Software Developer