Scribble 6: Trapping Rain Water

This is a really interesting problem. Here’s the problem statement:

Given an array of integers that represent the heights of mud walls built next to each other by the little children at a village school. The length and width of each wall is 1 unit. Find the volume of water that gets collected in the wall clefts after a full evening of rain.

Let’s dive into the solution:

It is good to realise that the total amount of water collected is the sum of the amounts of water collected at each index. Therefore we need to find the amount of water collected at every index i in the array.

Note that the water collected at any particular index is a vertical column which is a part of the water area that is formed by: the tallest wall on the index’s left, the tallest wall on the index’s right and the wall tops that lie in between them. Also note that the maximum height possible for this water area = min(height of the tallest wall on the index’s left, the tallest wall on the index’s right).

Therefore the amount of water collected at this index = (min(height of the tallest wall on the index’s left, the tallest wall on the index’s right)-height[i])*wallLength*wallWidth

Approach1:

This is a naive method. Here’s the steps:

set totalWater = 0

Loop through all indices in the array using a for loop.
At every index:
- move towards its left till the 0^th index and find the tallest wall to its left, store it in maxLeft
- move towards its right till the last index and find the tallest wall to its right, store it in maxRight
- set water collected at this index = (min(maxLeft, maxRight)-height[i])*wallLength*wallWidth
- set totalWater += water collected at this index

Time complexity: O(N²) because at every index i (where i goes from 0 to n), we loop over all indices in the array. Therefore, totally, we loop over N² indices throughout the algorithm.

Space complexity: O(1) because we do not use any extra storage space.

Here’s the code for this solution in Java:

public int trap(int[] height) {

    int maxLeft, maxRight, totalWater, water, wallWidth, wallLength;
    maxLeft = maxRight = totalWater = water = 0;
    wallWidth = wallLength = 1;
    for(int i=1;i<=height.length-2;i++) {
        maxLeft = maxRight = water = 0;
    //note that no water will be stored above the 0th and the last walls because they do not have a left and a right wall respectively to hold any water
        for(int j = i-1;j>=0;j--) {
            maxLeft = Math.max(maxLeft, height[j]); 
        }
        for(int j = i+1;j<height.length;j++) {
            maxRight = Math.max(maxRight, height[j]); 
        }
        water = Math.min(maxLeft, maxRight)-height[i]*wallLength*wallWidth;
        totalWater += Math.max(water, 0);//we use Math.max(..,0) so as to prevent a -ve value from being added to totalWater
    }
    return totalWater;    
}

Approach 2:

Let’s see if we can do better than O(N²) this time using some space. How about we do this:

Loop over the array from left to right storing at every index the length of the tallest wall to the left of this array in another array leftHeight[]. Note that the length of the tallest wall to the left of index i will be the max of the length of the tallest wall to the left of index (i-1) and the length of wall at the (i-1)^th index i.e. leftHeight[i] = max(leftHeight[i-1],height[i-1])
Next, loop over the array one more time from the right to the left keeping variable maxRight to store the length of the tallest wall to the right of every index. maxRight can be set at the i^th index for the next index i.e. for the (i-1)^th index as: maxRight = max(old value of maxRight that represents the length of the tallest wall to the right og the i^th index, height[i]). Along With this, at every index calculate the amount of water stored at the index as = (min(maxLeft[i], maxRight)-height[i])*wallLength*wallWidth and update totalWater. For the last index, maxRight = 0 and therefore water stored at it will be calculated to be 0.

Time complexity: O(N) because every element is visited only twice throughout the algorithm

Space complexity: O(N) because we use an extra array leftHeight.

Here is the solution for this problem coded in Java:

public int trap(int[] height) {

    int leftHeight[] = new int[height.length]; 
    leftHeight[0] = 0;
    int wallWidth, wallLength;
    wallWidth = wallLength = 1;
    //note that no water will be stored above the 0th wall because it doesn't have a left wall to hold any water
    for(int i=1;i<height.length;i++) {
        leftHeight[i] = Math.max(leftHeight[i-1], height[i-1]);
    }
    //height[height.length-1] = Math.max(leftHeight[height.length] - [height.length],0);
    int maxRight = 0;
    int totalWater = 0;
    for(int i=height.length-1;i>=0;i--) {//note that no water will be stored above the last wall because it doesn't have a right wall to hold any water
        totalWater+= Math.max(Math.min(leftHeight[i], maxRight)*wallLength*wallWidth - height[i],0);/*we use Math.max(..,0) so as to prevent a -ve value from being added to totalWater*/
		maxRight = Math.max(maxRight, height[i]);
        
    }
    return totalWater;
}

Note that there are more efficient solutions to this problem that we’ll be uploading soon here. Stay tuned to not miss the update.

Please do let me know if you find this article useful. Also, it’ll be great if you’d provide some feedback. To reach out, please leave a comment in the Contact section. Thanks! Happy Coding! 🙂

Share this:

Related