Skip to content

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;
}

Comments