Trapping Rain Water hard

Problem Statement

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

Steps to Solve

The core idea is to find, for each bar, the maximum water level it can trap. This level is determined by the maximum height of the bars to its left and right. The trapped water for that bar is the minimum of these maximum heights minus the bar's height. We sum this up for all bars.

We can achieve this efficiently using two arrays:

  1. leftMax: Stores the maximum height encountered so far from the left side, for each index.
  2. rightMax: Stores the maximum height encountered so far from the right side, for each index.

Then, for each bar:

  1. Calculate min(leftMax[i], rightMax[i]). This represents the maximum water level possible at index i.
  2. Subtract the bar's height (height[i]) from this maximum water level. This gives the trapped water at index i.
  3. Sum up the trapped water for all indices.

Explanation

Let's break it down using Example 1: height = [0,1,0,2,1,0,1,3,2,1,2,1]

  1. leftMax: Iterate from left to right. leftMax[i] will be the maximum of all elements from height[0] to height[i]. This gives: [0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3]

  2. rightMax: Iterate from right to left. rightMax[i] will be the maximum of all elements from height[n-1] to height[i]. This gives: [3, 3, 3, 3, 3, 3, 2, 3, 2, 2, 2, 1]

  3. Trapped Water Calculation: Now, for each index i:

    • min(leftMax[i], rightMax[i]) - height[i] gives the trapped water at that index.
    • Sum up these values to get the total trapped water.

Code (Typescript)

function trap(height: number[]): number {
    const n = height.length;
    if (n === 0) return 0;

    const leftMax: number[] = new Array(n).fill(0);
    const rightMax: number[] = new Array(n).fill(0);

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

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

    let trappedWater = 0;
    for (let i = 0; i < n; i++) {
        trappedWater += Math.max(0, Math.min(leftMax[i], rightMax[i]) - height[i]);
    }

    return trappedWater;
};

Complexity

  • Time Complexity: O(n), where n is the length of the height array. We iterate through the array three times.
  • Space Complexity: O(n), due to the leftMax and rightMax arrays. We could potentially optimize this to O(1) using two pointers, but that approach is slightly more complex to understand.