# Trapping Rain Water Problem
#### Given an array representing the heights of buildings, the task is to calculate the total amount of water trapped between the buildings.

Observations:

* To calculate the total amount of water, we need to determine the amount of water trapped above each building.
* The amount of water trapped above a building depends on the presence of taller buildings on its left and right sides.
* A building cannot trap water if there is no taller building on its left side.
* A building can trap water if it has taller buildings on both its left and right sides.
* The height of the water column trapped above a building is the minimum of the maximum heights on its left and right sides, minus its own height.

#### Approach to solve the problem

* For each building, calculate the maximum height on its left side (leftMax).
* For each building, calculate the maximum height on its right side (rightMax).
* For each building, calculate the height of the water column trapped above it using the formula: min(leftMax, rightMax) - height of the building.
* Sum up the heights of all the water columns calculated in the previous step to get the total amount of trapped water.

Example

* Given heights: [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
* Calculate the maximum heights on the left side and store them in an array: [0, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3]
* Calculate the maximum heights on the right side and store them in an array: [3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 0]
* Calculate the height of the water column trapped above each building using the formula: [0, 0, 1, 0, 1, 2, 1, 0, 0, 1, 0, 0]
* Sum up the heights of all the water columns: 6 units of water are trapped.

Pseudocode:

Function calculateTrappedWater(heights):
n = length of heights
Initialize an array leftMax of size n
Initialize an array rightMax of size n
leftMax[0] = heights[0]
rightMax[n-1] = heights[n-1]

for i = 1 to n-1:
    leftMax[i] = max(leftMax[i-1], heights[i-1])

for i = n-2 to 0:
    rightMax[i] = max(rightMax[i+1], heights[i+1])

totalWater = 0

for i = 0 to n-1:
    waterAbove = min(leftMax[i], rightMax[i]) - heights[i]
    totalWater += waterAbove

return totalWater

#### Complexity Analysis

* Time Complexity: O(n) - We iterate through the array once to calculate leftMax and rightMax, and once to calculate the water trapped above each building.
* Space Complexity: O(n) - We use additional space to store the leftMax and rightMax arrays.

#### Conclusion

*The Trapping Rain Water problem can be solved by calculating the maximum heights on the left and right sides of each building and then summing up the heights of the water columns above each building.
Understanding the problem, making observations, and applying the formula can lead to an efficient solution.*