Trapping Water Hard

Problem Statement

Given an array, where each element in the array represents the height of each bar at that position. We have to determine how much water can be trapped in the given elevation map.
Eg:

Algorithm Ideation:

In order to determine how much water we can trap in each position, we need to know the maximum elements to the left and right of the given position.
For Eg. If we consider the position 2 in the given problem:

Here, the min of Lmax and Rmax is 2.
So, Volume occupied at position 2 is 2 - 0 = 2.

Similarly for position 4:

Volume = Min(3, 3) - E[4] = 3 - 1 = 0.

Hence, we just need to find the maximum element to the left and right of the given element.

Approach 1: Dynamic Programming.

Time Complexity: O(n)
Space Complexity: O(n)

We can create 2 arrays, Lmax and Rmax which will store the maximum element to the left and right of the current element respectively in the given array.
We have another array that will hold the Min(LMax, RMax) in each position.
Once we have the Min(LMax, RMax) array, we can iterate through the array. The volume present in each position will be Min(Lmax, Rmax) - Element at i.
Here, Min(LMax, RMax) - Element at i = 0 - 0 = 0; So No volume is added.
Here, we have got a negative value as volume, which means current tower height is greater than its maximum surrounding towers, in this case we skip as no volume can be filled here.
Negative volumes can similarly be skipped in all positions, if occurs.
Here, we got a positive volume (2), hence we can add it to the final volume.
Negative Volume, Can be skipped.
Volume here is 2, we add it to the result.
Calculated Volume is 3, we add to the result.
Calculated Volume is 2, we add to the result.
Negative Volume, Can be skipped.
Negative Volume, Can be skipped.
Negative Volume, Can be skipped.
After iterating through the entire array, we get volume to be 9.

Approach 2: Two Pointers

Time Complexity: O(n)
Space Complexity: O(1)

Ideally, we can avoid the space needed in DP.
We initialize 2 pointers L and R, which start at 0 and n-1 respectively, where n is the length of the array.
We also initialize 2 variables, lmax and rmax which are initially set to 0.
lmax will store the max element from the left end until element at pointer L.
rmax will store the max element from the right end until element at pointer R.
In each iteration, We check which is smallest among lmax and rmax in each iteration.
If lmax is smallest, we are sure that there exists an rmax to the right of i, which is larger, so for the current iteration, consider lmax as Min(Lmax, Rmax) deduct element at L from it.
This way we get the volume occupied at L. Once this is done, we increment lmax.
Similarly, If rmax is smallest, we are sure that there exists an lmax to the left of i, which is larger, so for the current iteration, consider rmax as Min(Lmax, Rmax) deduct element at R from it.
This way we get the volume occupied at R. Once this is done, we decrement rmax.
Here, Lmax <= Rmax, Volume at L = 0, incrementing L.
Lmax <= Rmax, Volume at L is -2, we ignore negative values, Incrementing L and updating Lmax to 2.
Here, Rmax < Lmax, so we calculate the volume at R. Since it’s negative, we ignore and decrement R, Also update rmax to 1.
Still Rmax < Lmax, so we Volume at R = -1, Ignore and decrement R, Update Rmax to 2.
Lmax <= Rmax, so we calculate volume at L (2). Since it’s positive, we add to volume, increment L and proceed.
Lmax <= Rmax, Volume at L = -1, Negative, Ignore, Increment L, Update Lmax to 3.
Rmax < Lmax, So Volume at R = -1, Ignore, Decrement R, Update Rmax to 3.
Lmax <= Rmax, So Volume at L = 2. Add to volume, Increment L and proceed.
Lmax <= Rmax, Volume at L = 3. Add to volume, Increment L and proceed.
Lmax <= Rmax. Volume at L = 2. Add to volume, Increment L and proceed.
At this point, L has crossed R. We know that Volumes to the right of R are already calculated. So we stop the iteration here and return the calculated volume.

Code

Dynamic Programming

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int[] maxLeft = new int[n];
        int[] maxRight = new int[n];

        int volume = 0;
        
        int currMaxLeft = 0;
        for (int i = 0; i < n; i++) {
            maxLeft[i] = currMaxLeft;
            currMaxLeft = Math.max(height[i], currMaxLeft);
        }

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

        for (int i = 0; i < n; i++) {
            int minSurroundingHeight = Math.min(maxLeft[i], maxRight[i]);
            int volumeI = Math.max(minSurroundingHeight - height[i], 0);
            volume += volumeI;
        }

        return volume;
    }
}

Two Pointer

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int volume = 0;

        int l = 0;
        int r = n - 1;
        int lmax = 0;
        int rmax = 0;
        while(l <= r) {

            if (lmax < rmax) {
                int h = height[l++];
                int volumeI = Math.max(0, lmax - h);
                volume += volumeI;
                lmax = Math.max(lmax, h);
            } else {
                int h = height[r--];
                int volumeI = Math.max(0, rmax - h);
                volume += volumeI;
                rmax = Math.max(rmax, h);
            }
        }   

        return volume;
    }
}