# 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 ApproachThe 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:O(n*n)O(1)C++ Implementation:Output2) Efficient ApproachWe will use precomputed values of height in two arrays left and right.

Initially

value will be same asleft[0]as there are no other element left of it andleft[0]=arr[0]will beright[n-1]as there is no other right element. For other elements we will takearr[n-1]as the sum of water.min(left[i],right[i])-arr[i]Pseudo Code:O(n)O(n)C++ Implementation:Output