Coding-Trapping rain water

Given an array of integers represents height of building, width of each building is 1. Compute the amount of water it can trap after raining.

Example :height = [0,1,0,2,1,0,1,3,2,1,2,1] answer is 6 units

Intuitive solution: Find max height from left to right and right to left for each position in array, let’s call these arrays as leftMax[] and rightMax[]

Once we have leftMax and rightMax for every index, we can easily calculate result which minimum of leftMax and rightMax minus current tower height.

Complete code

Great we have a solution Time complexity is O(N) and space complexity is also O(N). At this point interviewer will ask a follow up question.

Can we solve this problem with O(1) space complexity?

This is tricky!!!

To solve this problem without using additional space, we need to make an observation in our first solution.

Observe this line of code

area += Math.min(leftMax[i], rightMax[i]) — height[i];

area depends on either leftMax or rightMax which ever is smaller. So if for a given index suppose we know that there is a larger element on the right side than our result will only depends on leftMax, we don’t need to know the rightMax for that index.

If there is a larger bar at one end (say right), we are assured that the water trapped would be dependant on height of bar in current direction (from left to right). As soon as we find the bar at other end (right) is smaller, we start iterating in opposite direction (from right to left).

So what should we do?

We can maintain two pointers left and right pointing to first and last elements of the array and we will also maintain leftMax and rightMax. At every point we can check if left element is smaller than right element then leftMax will contribute to our result else rightMax will contribute.

Lets try to understand it with code

O(1) space complexity solution.

There is another interesting solution using stack, which helps in understanding the applications of stack.

We can maintain bounded elements (elements which has bigger elements on left and right side) in a stack.

We maintain elements in stack in decreasing order, i.e if current element is smaller than top elements of stack we will add current element to stack. If current element is bigger than top element of stack than the top element is bounded by the current element and the previous elements of stack so we take out the top element and calculate the bounded height and distance between bounded buildings and calculate trapped water.

Stack solution

Thank you for reading

Keep coding !!!