Leetcode trapping water

stuff about computer science and programming
Post Reply
User avatar
dendiz
Site Admin
Posts: 234
Joined: Wed Oct 10, 2018 3:48 am

Leetcode trapping water

Post by dendiz » Wed Jan 16, 2019 8:29 am

Given an array of positive integers which define a histogram, find out how much water would be trapped if it rained on it.

Here is an image explaining the situation
2019-01-16 00_14_42-Window.png
The blue squares are the water trapped and the black are the bars trapping the water, the green numbers are the array values representing the heights.

The key observation here is that the max height bar will trap water depending on the max bars (relative to it self) on its right and left side.
Another observation is that the bar at location 'i' will trap water (minimum of [highest bar on right, higiest bar on left] - my own height) of water.
2019-01-16 00_23_47-Window.png
So here what we need to do:
  • for each bar:
    1. find the height of the highest bar on the right
    2. find the height of the highest bar on the left
    3. total = min(rightmax, leftmax) - my height
Now if we scan each time for the left and right max the time complexity will become n^2. So to fix that we can precompute the max heights
for an index and onwards

Code: Select all

        for(int i=0;i<height.length;i++) {
            curMax = Math.max(height[i], curMax);
            leftMax[i] = curMax;
        }
for the input array

Code: Select all

2,1,2,1,3,0,2,1,3
the left max array will be

Code: Select all

2,2,2,2,3,3,3,3,3
do the same for the right max and we have a nice lookup table in o(n) time.

now just apply the algorithm above:

Code: Select all

    public int trap(int[] height) {
        int[] leftMax = new int[height.length];
        int[] rightMax = new int[height.length];
        
        int curMax = -1;
        for(int i=0;i<height.length;i++) {
            curMax = Math.max(height[i], curMax);
            leftMax[i] = curMax;
        }
        
        curMax = -1;
        for(int i=height.length-1;i>=0;i--) {
            curMax = Math.max(height[i], curMax);
            rightMax[i] = curMax;
        }
        
       
        
        int sum = 0;
        for(int i =0;i<height.length;i++) {
            sum += Math.min(rightMax[i], leftMax[i]) - height[i];
        }
        
        return sum;
    }

Post Reply