Trapping Rain Water

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.

Input/Output Specifications

• Input: An array height where n == height.length and 0 <= height[i] <= 10^5
• Output: An integer representing the total amount of rainwater that can be trapped

Constraints

• n == height.length
• 1 <= n <= 2 * 10^4
• 0 <= height[i] <= 10^5

Examples

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rainwater (blue section) are being trapped.

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9
Explanation: 9 units of rainwater are trapped.

Example 3:

Input: height = [3,0,2,0,4]
Output: 7
Explanation: 7 units of rainwater are trapped.

Solution Approaches

Approach 1: Two Pointers (Optimal)

Algorithm Explanation: The key insight is that the amount of water trapped at any position depends on the minimum of the maximum heights to the left and right of that position. We can use two pointers to track the maximum heights from both ends.

1. Use two pointers: left and right
2. Track maximum heights from left and right
3. Move the pointer with smaller maximum height
4. Calculate trapped water at each position

Implementation:

Python:

def trap(height):
    """
    Calculate trapped rainwater using two pointers
    Time: O(n)
    Space: O(1)
    """
    if not height or len(height) < 3:
        return 0
    
    left, right = 0, len(height) - 1
    left_max = right_max = 0
    water_trapped = 0
    
    while left < right:
        if height[left] < height[right]:
            if height[left] >= left_max:
                left_max = height[left]
            else:
                water_trapped += left_max - height[left]
            left += 1
        else:
            if height[right] >= right_max:
                right_max = height[right]
            else:
                water_trapped += right_max - height[right]
            right -= 1
    
    return water_trapped

Java:

class Solution {
    /**
     * Calculate trapped rainwater using two pointers
     * Time: O(n)
     * Space: O(1)
     */
    public int trap(int[] height) {
        if (height == null || height.length < 3) {
            return 0;
        }
        
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        int waterTrapped = 0;
        
        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] >= leftMax) {
                    leftMax = height[left];
                } else {
                    waterTrapped += leftMax - height[left];
                }
                left++;
            } else {
                if (height[right] >= rightMax) {
                    rightMax = height[right];
                } else {
                    waterTrapped += rightMax - height[right];
                }
                right--;
            }
        }
        
        return waterTrapped;
    }
}

Go:

// trap - Calculate trapped rainwater using two pointers
// Time: O(n)
// Space: O(1)
func trap(height []int) int {
    if len(height) < 3 {
        return 0
    }
    
    left, right := 0, len(height)-1
    leftMax, rightMax := 0, 0
    waterTrapped := 0
    
    for left < right {
        if height[left] < height[right] {
            if height[left] >= leftMax {
                leftMax = height[left]
            } else {
                waterTrapped += leftMax - height[left]
            }
            left++
        } else {
            if height[right] >= rightMax {
                rightMax = height[right]
            } else {
                waterTrapped += rightMax - height[right]
            }
            right--
        }
    }
    
    return waterTrapped
}

JavaScript:

/**
 * Calculate trapped rainwater using two pointers
 * Time: O(n)
 * Space: O(1)
 */
function trap(height) {
    if (!height || height.length < 3) {
        return 0;
    }
    
    let left = 0, right = height.length - 1;
    let leftMax = 0, rightMax = 0;
    let waterTrapped = 0;
    
    while (left < right) {
        if (height[left] < height[right]) {
            if (height[left] >= leftMax) {
                leftMax = height[left];
            } else {
                waterTrapped += leftMax - height[left];
            }
            left++;
        } else {
            if (height[right] >= rightMax) {
                rightMax = height[right];
            } else {
                waterTrapped += rightMax - height[right];
            }
            right--;
        }
    }
    
    return waterTrapped;
}

C#:

public class Solution {
    /// <summary>
    /// Calculate trapped rainwater using two pointers
    /// Time: O(n)
    /// Space: O(1)
    /// </summary>
    public int Trap(int[] height) {
        if (height == null || height.Length < 3) {
            return 0;
        }
        
        int left = 0, right = height.Length - 1;
        int leftMax = 0, rightMax = 0;
        int waterTrapped = 0;
        
        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] >= leftMax) {
                    leftMax = height[left];
                } else {
                    waterTrapped += leftMax - height[left];
                }
                left++;
            } else {
                if (height[right] >= rightMax) {
                    rightMax = height[right];
                } else {
                    waterTrapped += rightMax - height[right];
                }
                right--;
            }
        }
        
        return waterTrapped;
    }
}

Complexity Analysis:

• Time Complexity: O(n) - Single pass through the array
• Space Complexity: O(1) - Only using constant extra space

Trade-offs:

• Optimal time and space complexity
• Elegant two-pointer approach
• Requires understanding of the water trapping principle
• Most efficient solution

Approach 2: Dynamic Programming

Algorithm Explanation: Precompute the maximum heights to the left and right of each position, then calculate trapped water at each position.

1. Create arrays to store maximum heights from left and right
2. Calculate left maximums from left to right
3. Calculate right maximums from right to left
4. For each position, trapped water = min(leftMax, rightMax) - heighti

Implementation:

Python:

def trapDP(height):
    """
    Calculate trapped rainwater using dynamic programming
    Time: O(n)
    Space: O(n)
    """
    if not height or len(height) < 3:
        return 0
    
    n = len(height)
    left_max = [0] * n
    right_max = [0] * n
    
    # Calculate maximum heights from left
    left_max[0] = height[0]
    for i in range(1, n):
        left_max[i] = max(left_max[i-1], height[i])
    
    # Calculate maximum heights from right
    right_max[n-1] = height[n-1]
    for i in range(n-2, -1, -1):
        right_max[i] = max(right_max[i+1], height[i])
    
    # Calculate trapped water
    water_trapped = 0
    for i in range(n):
        water_trapped += min(left_max[i], right_max[i]) - height[i]
    
    return water_trapped

Java:

class Solution {
    /**
     * Calculate trapped rainwater using dynamic programming
     * Time: O(n)
     * Space: O(n)
     */
    public int trapDP(int[] height) {
        if (height == null || height.length < 3) {
            return 0;
        }
        
        int n = height.length;
        int[] leftMax = new int[n];
        int[] rightMax = new int[n];
        
        // Calculate maximum heights from left
        leftMax[0] = height[0];
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.max(leftMax[i-1], height[i]);
        }
        
        // Calculate maximum heights from right
        rightMax[n-1] = height[n-1];
        for (int i = n-2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i+1], height[i]);
        }
        
        // Calculate trapped water
        int waterTrapped = 0;
        for (int i = 0; i < n; i++) {
            waterTrapped += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
        
        return waterTrapped;
    }
}

Go:

// trapDP - Calculate trapped rainwater using dynamic programming
// Time: O(n)
// Space: O(n)
func trapDP(height []int) int {
    if len(height) < 3 {
        return 0
    }
    
    n := len(height)
    leftMax := make([]int, n)
    rightMax := make([]int, n)
    
    // Calculate maximum heights from left
    leftMax[0] = height[0]
    for i := 1; i < n; i++ {
        leftMax[i] = max(leftMax[i-1], height[i])
    }
    
    // Calculate maximum heights from right
    rightMax[n-1] = height[n-1]
    for i := n-2; i >= 0; i-- {
        rightMax[i] = max(rightMax[i+1], height[i])
    }
    
    // Calculate trapped water
    waterTrapped := 0
    for i := 0; i < n; i++ {
        waterTrapped += min(leftMax[i], rightMax[i]) - height[i]
    }
    
    return waterTrapped
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

JavaScript:

/**
 * Calculate trapped rainwater using dynamic programming
 * Time: O(n)
 * Space: O(n)
 */
function trapDP(height) {
    if (!height || height.length < 3) {
        return 0;
    }
    
    const n = height.length;
    const leftMax = new Array(n);
    const rightMax = new Array(n);
    
    // Calculate maximum heights from left
    leftMax[0] = height[0];
    for (let i = 1; i < n; i++) {
        leftMax[i] = Math.max(leftMax[i-1], height[i]);
    }
    
    // Calculate maximum heights from right
    rightMax[n-1] = height[n-1];
    for (let i = n-2; i >= 0; i--) {
        rightMax[i] = Math.max(rightMax[i+1], height[i]);
    }
    
    // Calculate trapped water
    let waterTrapped = 0;
    for (let i = 0; i < n; i++) {
        waterTrapped += Math.min(leftMax[i], rightMax[i]) - height[i];
    }
    
    return waterTrapped;
}

C#:

public class Solution {
    /// <summary>
    /// Calculate trapped rainwater using dynamic programming
    /// Time: O(n)
    /// Space: O(n)
    /// </summary>
    public int TrapDP(int[] height) {
        if (height == null || height.Length < 3) {
            return 0;
        }
        
        int n = height.Length;
        int[] leftMax = new int[n];
        int[] rightMax = new int[n];
        
        // Calculate maximum heights from left
        leftMax[0] = height[0];
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.Max(leftMax[i-1], height[i]);
        }
        
        // Calculate maximum heights from right
        rightMax[n-1] = height[n-1];
        for (int i = n-2; i >= 0; i--) {
            rightMax[i] = Math.Max(rightMax[i+1], height[i]);
        }
        
        // Calculate trapped water
        int waterTrapped = 0;
        for (int i = 0; i < n; i++) {
            waterTrapped += Math.Min(leftMax[i], rightMax[i]) - height[i];
        }
        
        return waterTrapped;
    }
}

Complexity Analysis:

• Time Complexity: O(n) - Three passes through the array
• Space Complexity: O(n) - Two additional arrays of size n

Trade-offs:

• More intuitive approach
• Higher space complexity
• Easier to understand and implement
• Good stepping stone to two-pointer approach

Approach 3: Stack-based Solution

Algorithm Explanation: Use a stack to keep track of indices of bars. When we find a bar that's higher than the bar at the top of the stack, we can trap water.

Implementation:

Python:

def trapStack(height):
    """
    Calculate trapped rainwater using stack
    Time: O(n)
    Space: O(n)
    """
    if not height or len(height) < 3:
        return 0
    
    stack = []
    water_trapped = 0
    
    for i in range(len(height)):
        while stack and height[i] > height[stack[-1]]:
            top = stack.pop()
            if not stack:
                break
            
            distance = i - stack[-1] - 1
            bounded_height = min(height[i], height[stack[-1]]) - height[top]
            water_trapped += distance * bounded_height
        
        stack.append(i)
    
    return water_trapped

Java:

class Solution {
    /**
     * Calculate trapped rainwater using stack
     * Time: O(n)
     * Space: O(n)
     */
    public int trapStack(int[] height) {
        if (height == null || height.length < 3) {
            return 0;
        }
        
        Stack<Integer> stack = new Stack<>();
        int waterTrapped = 0;
        
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                int top = stack.pop();
                if (stack.isEmpty()) {
                    break;
                }
                
                int distance = i - stack.peek() - 1;
                int boundedHeight = Math.min(height[i], height[stack.peek()]) - height[top];
                waterTrapped += distance * boundedHeight;
            }
            stack.push(i);
        }
        
        return waterTrapped;
    }
}

Complexity Analysis:

• Time Complexity: O(n) - Each element pushed and popped once
• Space Complexity: O(n) - Stack can contain up to n elements

Trade-offs:

• Different approach using stack
• More complex to understand
• Same time complexity as DP
• Useful for understanding stack applications

Key Insights

• Water Trapping Principle: Water trapped at position i = min(max_left, max_right) - heighti
• Two Pointer Optimization: We only need to know the minimum of left and right maximums
• Greedy Approach: Move the pointer with smaller maximum height
• Stack Pattern: Useful for problems involving "next greater element" type scenarios

Edge Cases

1. Empty Array: [] → Returns 0
2. Single Element: [5] → Returns 0
3. Two Elements: [5, 3] → Returns 0
4. Ascending Heights: [1, 2, 3, 4, 5] → Returns 0
5. Descending Heights: [5, 4, 3, 2, 1] → Returns 0
6. All Same Heights: [3, 3, 3, 3] → Returns 0

How Solutions Handle Edge Cases:

• Early return for arrays with less than 3 elements
• Two-pointer approach handles all cases naturally
• DP approach explicitly calculates for each position
• Stack approach processes each element correctly

Test Cases

def test_trap():
    # Test case 1
    assert trap([0,1,0,2,1,0,1,3,2,1,2,1]) == 6
    
    # Test case 2
    assert trap([4,2,0,3,2,5]) == 9
    
    # Test case 3
    assert trap([3,0,2,0,4]) == 7
    
    # Edge cases
    assert trap([]) == 0
    assert trap([5]) == 0
    assert trap([5, 3]) == 0
    assert trap([1, 2, 3, 4, 5]) == 0
    assert trap([5, 4, 3, 2, 1]) == 0
    assert trap([3, 3, 3, 3]) == 0
    
    print("All tests passed!")

test_trap()

Follow-up Questions

1. Container With Most Water: How would you find two lines that together with x-axis forms a container that holds the most water?
2. Largest Rectangle: How would you find the largest rectangle that can be formed in a histogram?
3. 3D Trapping: What if the elevation map was 3D instead of 2D?
4. Streaming Data: How would you handle this problem with streaming height data?
5. Multiple Peeks: What if there were multiple peaks of the same height?

Common Mistakes

1. Not Handling Edge Cases: Forgetting arrays with less than 3 elements
   • Problem: Incorrect results for small arrays
   • Solution: Add early return for small arrays
2. Wrong Water Calculation: Not understanding the min(leftMax, rightMax) principle
   • Problem: Incorrect water calculation
   • Solution: Understand that water level is limited by the shorter wall
3. Index Out of Bounds: Not handling stack operations correctly
   • Problem: Runtime errors in stack approach
   • Solution: Check stack emptiness before operations
4. Infinite Loop: Not updating pointers correctly in two-pointer approach
   • Problem: Algorithm doesn't terminate
   • Solution: Ensure pointers always move toward each other

Interview Tips

1. Start with Examples: Draw the elevation map and show water trapping
2. Explain the Principle: Clarify why water trapped = min(leftMax, rightMax) - heighti
3. Discuss Approaches: Start with DP, then optimize to two pointers
4. Handle Edge Cases: Always mention empty arrays and small arrays
5. Visualize: Draw the two-pointer movement to show the algorithm

Concept Explanations

Two Pointer Technique: This problem demonstrates advanced two-pointer usage where we track maximum values and make decisions based on comparisons.

Dynamic Programming: The DP approach shows how to precompute information to solve the problem efficiently.

Stack Applications: The stack approach demonstrates how stacks can be used for problems involving "next greater element" patterns.

Water Trapping Physics: Understanding the physical principle that water level is determined by the shorter of the two containing walls is crucial for solving this problem.