42. Trapping Rain Water

Intitution

To trap water between the bars, we need to know the maximum height to the left and to the right of each bar.

• The water that a bar can trap = min(leftMax, rightMax) - heightAtBar, as long as this value is positive.

We traverse twice:

1. Right to left to build an array of right max heights.

2. Left to right to calculate trapped water using current height and right max.

Complexity

Space Complexity	Time Complexity
$\text{O}(N)$	$\text{O}(N)$

Code

public int trap(int[] elevationHeights) {
    int n = elevationHeights.length;

    // Array to store the maximum height to the right of each bar
    int[] maxHeightToRight = new int[n];

    int maxSoFar = 0;
    // Traverse from right to left to fill maxHeightToRight
    for (int i = n - 1; i >= 0; --i) {
        maxHeightToRight[i] = maxSoFar;
        maxSoFar = Math.max(elevationHeights[i], maxSoFar);
    }

    int totalTrappedWater = 0;
    maxSoFar = 0; // Reuse for max height to the left

    // Traverse from left to right to compute trapped water
    for (int i = 0; i < n; ++i) {
        // Water that can be stored at current index
        int waterAtCurrent = Math.min(maxSoFar, maxHeightToRight[i]) - elevationHeights[i];

        // Only count if it's a positive amount of water
        if (waterAtCurrent > 0) {
            totalTrappedWater += waterAtCurrent;
        }

        maxSoFar = Math.max(elevationHeights[i], maxSoFar);
    }

    return totalTrappedWater;
}