L8. Trapping Rainwater | 2 Approaches | Stack and Queue Playlist

A comprehensive study note on solving the classic Trapping Rainwater DSA problem, exploring both the optimized prefix/suffix array approach ($\mathcal{O}(N)$ time, $\mathcal{O}(N)$ space) and the optimal two-pointer approach ($\mathcal{O}(N)$ time, $\mathcal{O}(1)$ space).

1. Why Do We Need This? (Problem Statement & Status Quo)

Imagine you are given an array of non-negative integers representing the heights of buildings (where a height can also be $0$). If it rains, water falls from the sky, causing water logging in between the buildings.

Heights: [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

Water trapped between buildings:
   _
  | |   _   _
  | |_.| |_| |_.   _
 _|_|_|_|_|_|_|_|_| |_

• Flat Surfaces vs. Pockets: Water does not get logged on flat surfaces if there are no flanking boundaries; it simply flows off into the streets. Water is only trapped in between buildings where it is walled off on both sides.
• Goal: Calculate and return the total units of water stored across all building pockets.

2. Core Mental Model & Real-Life Analogy

Real-Life Analogy: Rainwater in a Mountain Valley

Think of the array as a series of uneven terrain or mountain peaks of varying heights. When rain falls, water fills up the depressions between peaks.

• For any given building (index i), can it hold water? It can only hold water if there is a taller building somewhere on its left AND a taller building somewhere on its right.
• The Limiting Wall Constraint: The water level above any building cannot exceed the shorter of the two bounding heights (the left maximum height vs. the right maximum height). If water goes higher than the shorter bounding wall, it simply overflows into the streets.

3. Naive vs. Better Approach: The Building-by-Building Intuition

To find the total units of water, we can break down the problem into individual buildings.

If we stand at any building i:

1. Look strictly to the left to find the tallest building (leftMax).
2. Look strictly to the right to find the tallest building (rightMax).
3. The water level sustained above building i is determined by the bottleneck: min(leftMax, rightMax).
4. Subtract the height of the current building itself (array[i]) to get the trapped units at that index:

Summing this calculation across all indices from $0$ to $N-1$ yields the total trapped rainwater. However, scanning left and right linearly for every single building results in an inefficient $\mathcal{O}(N^2)$ time complexity. We need a faster way to compute leftMax and rightMax.

4. Step-by-Step Evolution: Prefix Max & Suffix Max Arrays ($\mathcal{O}(N)$ Space)

To avoid repeated linear scans, we can pre-compute the maximum heights using auxiliary memory:

• Prefix Max Array: Stores the maximum height encountered from the left up to the current index.
• Suffix Max Array: Stores the maximum height encountered from the right down to the current index.

Prefix Max Construction Example

Given array: [2, 1, 0, 5, 3]

• At index 0: Max is 2
• At index 1: Max of (2, 1) is 2
• At index 2: Max of (2, 1, 0) is 2
• At index 3: Max of (2, 1, 0, 5) is 5
• At index 4: Max of (2, 1, 0, 5, 3) is 5

Prefix array: [2, 2, 2, 5, 5]

Suffix Max Construction Example

Given array: [10, 2, 11, 1]

• Traverse backwards from the last element.
• Suffix array: [11, 11, 11, 1]

Code Implementation (Prefix & Suffix Approach)

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        if (n == 0) return 0;
        
        int[] prefixMax = new int[n];
        int[] suffixMax = new int[n];
        
        // Fill Prefix Max array
        prefixMax[0] = height[0];
        for (int i = 1; i < n; i++) {
            prefixMax[i] = Math.max(prefixMax[i - 1], height[i]);
        }
        
        // Fill Suffix Max array
        suffixMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            suffixMax[i] = Math.max(suffixMax[i + 1], height[i]);
        }
        
        int totalWater = 0;
        for (int i = 0; i < n; i++) {
            int leftMax = prefixMax[i];
            int rightMax = suffixMax[i];
            
            if (height[i] < leftMax && height[i] < rightMax) {
                totalWater += Math.min(leftMax, rightMax) - height[i];
            }
        }
        
        return totalWater;
    }
}

5. Optimal Two-Pointer Approach ($\mathcal{O}(1)$ Space)

An interviewer will typically push you to optimize the space complexity from $\mathcal{O}(N)$ down to $\mathcal{O}(1)$ by eliminating the prefix and suffix arrays.

The Core Insight

• Notice that for any index, we only ever care about the shorter of the two bounding heights (leftMax or rightMax).
• If leftMax is smaller than or equal to rightMax, we are guaranteed that water retention at the left pointer is bounded securely by leftMax, regardless of whatever taller buildings exist further to the right.
• Conversely, if rightMax is smaller, water retention at the right pointer is securely bounded by rightMax.

Two-Pointer Execution Flow

1. Initialize left = 0 and right = n - 1.
2. Initialize leftMax = 0, rightMax = 0, and totalWater = 0.
3. While left <= right:
   • Compare height[left] and height[right].
   • Case A (height[left] <= height[right]): Process the left side because we have a taller supporting wall on the right.
     • If height[left] >= leftMax, update leftMax = height[left].
     • Else, add water: totalWater += leftMax - height[left].
     • Increment left++.
   • Case B (height[left] > height[right]): Process the right side because we have a taller supporting wall on the left.
     • If height[right] >= rightMax, update rightMax = height[right].
     • Else, add water: totalWater += rightMax - height[right].
     • Decrement right--.

6. Complete Flow Walkthrough (Two-Pointer Code)

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        if (n <= 2) return 0;
        
        int left = 0, right = n - 1;
        int leftMax = 0, rightMax = 0;
        int totalWater = 0;
        
        while (left <= right) {
            if (height[left] <= height[right]) {
                if (height[left] >= leftMax) {
                    leftMax = height[left];
                } else {
                    totalWater += leftMax - height[left];
                }
                left++;
            } else {
                if (height[right] >= rightMax) {
                    rightMax = height[right];
                } else {
                    totalWater += rightMax - height[right];
                }
                right--;
            }
        }
        
        return totalWater;
    }
}

7. Complexity Analysis Summary

Summary and Key Takeaways

• Water Logging Rule: Water is trapped only between buildings that have a taller boundary on both the left and the right sides.
• The Bottleneck Principle: The height of trapped water at any point is strictly limited by the shorter of the left maximum and right maximum walls: min(leftMax, rightMax) - height[i].
• Space Optimization Trick: By using two pointers (left and right) and tracking running maximums (leftMax and rightMax), we can process the smaller side first, rendering auxiliary arrays unnecessary.
• Optimal Efficiency: The two-pointer solution achieves $\mathcal{O}(N)$ time complexity and $\mathcal{O}(1)$ space complexity, which is the theoretical limit since every element must be visited at least once.