Problem

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9

Solution

Brute Force Approach

---

Left Maximum and Right Maximum**:

• For each building at index i, we want to find the maximum height on its left side (up to index i) and the maximum height on its right side (from index i onwards).

• These maximum heights will help us determine how much water the ith building can hold.

• Left Maximum Array:

  • To find the left maximum for each building, start from the leftmost building (index 0) and keep track of the maximum height seen so far.

  • As you move to the right, update the left maximum for each building.

  • For example, if the heights of the buildings are [3, 0, 2, 4, 1], the left maximum array would be [3, 3, 3, 4, 4].

• Right Maximum Array:

  • Similarly, traverse the buildings from right to left and keep track of the maximum height seen so far.

  • Update the right maximum for each building.

  • Using the same example, the right maximum array would be [4, 4, 4, 4, 1].

• Water Calculation:

  • Now that we have both the left maximum and right maximum arrays, we can calculate the water stored at each building.

  • For each building at index i, the water stored is given by: Water at i=min( leftMax[i], rightMax[i])

Intuition

In more technical terms, the intuition holds because the water trapped at any point (let’s say P3) is limited by the shorter of the left maximum (P1) and the right maximum (P7). If P1 is taller, P3 can’t store more water than P1’s height, even if there are other buildings in between.

Code

Time - O(n)

space -O(n)

class Solution {
    public int[] getLeftMax(int[] height){
        int n = height.length;
        int[] leftMax = new int[n];

        int max = -1;
        for(int i=0; i<n;i++){
            max = Math.max(max,height[i]);
            leftMax[i] = max;
        }
        return leftMax;
    }

    public int[] getRightMax(int[] height){
        int n = height.length;
        int[] rightMax = new int[n];

        int max = -1;
        for(int i=n-1; i>=0;i--){
            max = Math.max(max,height[i]);
            rightMax[i] = max;
        }
        return rightMax;
    }

    public int trap(int[] height) {

        int[] leftMax = getLeftMax(height);
        int[] rightMax = getRightMax(height);

        int total = 0;
        for(int i=0; i<height.length; i++){
            if(height[i]<leftMax[i] && height[i]<rightMax[i]){
                total+=(Math.min(leftMax[i], rightMax[i]) - height[i]);
            }
        }

        return total;
    }
}

Without left Max array

class Solution {

    public int[] getRightMax(int[] height){
        int n = height.length;
        int[] rightMax = new int[n];

        int max = -1;
        for(int i=n-1; i>=0;i--){
            max = Math.max(max,height[i]);
            rightMax[i] = max;
        }
        return rightMax;
    }

    public int trap(int[] height) {

        int leftMax = -1;
        int[] rightMax = getRightMax(height);

        int total = 0;
        for(int i=0; i<height.length; i++){
            leftMax = Math.max(leftMax, height[i]);

            if(height[i]<leftMax && height[i]<rightMax[i]){
                total+=(Math.min(leftMax, rightMax[i]) - height[i]);
            }
        }

        return total;
    }
}

Optimal Approach

We maintain two pointers, left and right. The left pointer starts at 0, and the right pointer starts at the end, n-1. We also keep track of the maximum heights seen so far from the left and right pointers. (Store it in leftMax and rightMax)

We calculate the rainwater that can be stored based on the smaller of the two pointers. If the left pointer is smaller, we calculate the rainwater at left index, move the left pointer to the next index, and similarly, if the right pointer is smaller, we calculate the rainwater at right index and move it to the previous index.

If the left pointer is smaller than the right pointer, it means that it can store water up to the maximum height seen by the left pointer (leftMax). This is because there cannot be any higher maximum on the left side that hasn’t already been accounted for. If there is any maximum on the right side yet to be pointed to by the right pointer, then also the current building can store water up to the leftMax height.

Similarly, if the right pointer is smaller than the left pointer, it means it can store water up to the maximum height seen by the right pointer so far rightMax.

At the end, the left and right pointers stop at the same index, which is the maximum element present in the array. The rainwater stored on top of the building is 0.

Code

Time - O(n)

Space -O(1)

class Solution {
    public int trap(int[] height) {
        int left = 0;
        int right = height.length - 1;

        int total = 0;

        int leftMax = 0;
        int rightMax = 0;

        while(left<right){
            if(height[left]<height[right]){
                if(leftMax>height[left]){
                    total += (leftMax-height[left]);
                }
                leftMax = Math.max(leftMax, height[left]);
                left+=1; 
            }
            else{
                if(rightMax>height[right]){
                    total+= (rightMax-height[right]);
                }
                rightMax = Math.max(rightMax, height[right]);
                right-=1;
            }
        }
        return total;
    }
}