Problem Statement

Given an a list of n integers which are non negative and represent an elevation map of various buildings where the width of each bar/building is 1, Find out how much water can be saved in between them when it rains.
Given an array {1,0,2,2,4,0,1,5,2,1,6,1} as input, the output should be 11

Solution Explanation

Imagine a series of buildings on the street where each building is of width 1 block and there are empty block spaces between some buildings. Also the heights of the buildings vary. When it rains, the free blocks between buildings and space between buildings can hold some water. The solution involves finding the amount of water between these buildings.

The most intutive brute force would be to find out at each block find the tallest one on the left and on the right and find out the difference between them.

For example, consider this,

    1 0 2

At '0', the difference between tallest one on the left and tallest one on the right is 1 (2 -1 ) which is the amount of water that can be saved in this combination.

Solving this would take finding max on the left and right at each index and so is exponential.

The brute force implementation looks like this,

    public class TrappingRainWater {

	public static void main(String[] args) {
		int[] heights = {1,0,2,2,4,0,1,5,2,1,3,1};
		System.out.println(bruteForce(heights));
	}
	
	public static int bruteForce(int[] heights){
		int result = 0, maxleft = 0, maxright = 0;
		int size = heights.length;
		for(int i=1;i<size-1;i++){
			maxleft = 0; maxright = 0;
			for(int j=i;j>=0;j--){
				maxleft = Math.max(maxleft, heights[j]);
			}
			for(int j=i;j<size-1;j++){
				maxright = Math.max(maxright, heights[j]);
			}
			result += Math.min(maxleft, maxright) - heights[i];
		}
		
		return result;
	}

}

When you run the above code, you would get the output as 11 which is the expected answer. But this would take O(n^2) time.

Let's try to optimize this. The concept we used was to find out left max and right max at each point, but instead we could use a single left max, right max while we traverse the array. We can use two pointers starting from the start and end, update the current max value for both and left if there's a new max, else find the difference of current element with max value.

Below is the Psuedo code for the above logic,

    left = 0, right = len(arr)-1
    maxwater = 0
    while left < right
     if(heights[left] < heights[right)
        if(heights[left]>leftmax)
            leftmax = heights[left]
        else
            maxwater += leftmax - heights[left]
     else
         if(heights[right] > rightmax) rightmax = heights[[right]
         else maxwater += rightmax - heights[right]

And below is the full java implementation for Trapping Rain Water,

class TrappingRainWater {
    public int trap(int[] height) {
        int left = 0, right = height.length-1;
        int maxleft = 0, maxright = 0;
        int result = 0;
        while(left <= right){
            if(height[left] < height[right]){
                if(height[left]>=maxleft) maxleft = height[left];
                else result += maxleft - height[left];
                left++;
            }
            else{
                if(height[right]>=maxright) maxright = height[right];
                else result+=maxright-height[right];
                right--;
            }
        }
        return result;
    }
}

Time Complexity

The time complexity is O(n^2) for the brute force, O(n) for the optimized approach.