#42

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Trapping Rain Water

Calculate the total trapped rain water using the elevation map array, leveraging dynamic programming and two-pointer patterns efficiently.

array two pointers dynamic programming stack monotonic stack

Problem Statement

You are given an array of non-negative integers representing an elevation map where the width of each bar is 1. The goal is to compute how much rain water can be trapped after raining. Each element in the array represents the height of a vertical bar, and water can only be trapped between higher bars. The challenge is to calculate the total units of trapped water efficiently using patterns like dynamic programming, two pointers, or stacks.

For example, consider an elevation map given by height = [0,1,0,2,1,0,1,3,2,1,2,1]. Water accumulates in valleys formed between bars, and the total trapped water for this input is 6 units. Constraints include arrays with length up to 20,000 and heights up to 100,000, making naive iteration inefficient. Correct handling of peaks, valleys, and plateaus is essential for accurate computation.

Examples

Example 1

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]

Output: 6

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 rain water (blue section) are being trapped.

Example 2

Input: height = [4,2,0,3,2,5]

Output: 9

Example details omitted.

Constraints

n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105

Solution Approach

Dynamic Programming with Precomputed Max Arrays

Compute two auxiliary arrays: left_max[i] storing the maximum height to the left of i, and right_max[i] storing the maximum height to the right. Then, iterate through the array and calculate trapped water at each index as min(left_max[i], right_max[i]) - height[i]. This method leverages the state transition dynamic programming pattern to avoid redundant calculations and guarantees O(n) time, though it uses O(n) extra space for the auxiliary arrays.

Two-Pointer Approach

Use two pointers starting at both ends of the elevation map, maintaining left_max and right_max variables. Move the pointer with the smaller height inward, updating max heights and accumulating water based on min(left_max, right_max) - height[i]. This method reduces space complexity to O(1) while still ensuring O(n) time. It directly handles valleys and peaks dynamically, reflecting the core state transition pattern of trapped water computation.

Monotonic Stack Approach

Iterate through the height array while maintaining a stack of indices in decreasing order. When the current height exceeds the stack top, pop the stack and calculate water trapped using the distance and bounded height. This approach effectively identifies local valleys and leverages the stack to model state transitions between peaks, achieving O(n) time with O(n) space. It handles irregular dips efficiently and prevents double-counting water units.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The solution can achieve O(n) time by visiting each bar once using dynamic programming, two-pointer, or stack approaches. Space complexity varies: O(n) for precomputed max arrays or stack, and O(1) for the optimized two-pointer approach. These complexities ensure scalable performance for input sizes up to 20,000 elements without unnecessary overhead.

What Interviewers Usually Probe

Do you understand why precomputing left and right max heights ensures correct trapped water calculation?
Can you explain how two-pointer traversal reduces space usage while maintaining accurate state transitions?
Will you handle edge cases where consecutive bars are equal or the array has a single peak?

Common Pitfalls or Variants

Common pitfalls

Failing to update left_max or right_max properly, causing underestimation of trapped water in valleys.
Confusing index distances when using the stack approach, leading to overcounting trapped units.
Assuming all dips trap water without considering the bounding higher bars, which results in incorrect totals.

Follow-up variants

Compute trapped water when elevation map elements are floating-point heights instead of integers.
Calculate trapped water using only constant extra space without modifying the original array.
Determine the maximum single valley water accumulation instead of total trapped water.

FAQ

How does the dynamic programming pattern apply to Trapping Rain Water?

Dynamic programming stores maximum heights to the left and right of each bar to calculate trapped water efficiently, avoiding repeated scans for each index.

Can I solve this problem with constant space?

Yes, the two-pointer approach maintains left_max and right_max variables only, achieving O(1) space while still computing trapped water correctly.

Why does the monotonic stack method work for this problem?

The stack identifies previous peaks and local valleys, modeling state transitions between bars and ensuring each trapped unit is counted precisely once.

What edge cases should I watch for in Trapping Rain Water?

Watch arrays with all equal heights, strictly increasing or decreasing heights, and single or multiple peaks that can cause zero or partial water trapping.

How do I calculate trapped water for irregular valleys?

Use precomputed left and right max or a stack to dynamically assess the bounding heights, ensuring even uneven dips are measured correctly for trapped water.

terminal

Solution

Solution 1: Dynamic Programming

We define $left[i]$ as the height of the highest bar to the left of and including the position at index $i$, and $right[i]$ as the height of the highest bar to the right of and including the position at index $i$. Therefore, the amount of rainwater that can be trapped at index $i$ is $min(left[i], right[i]) - height[i]$. We traverse the array to calculate $left[i]$ and $right[i]$, and the final answer is $\sum_{i=0}^{n-1} \min(left[i], right[i]) - height[i]$.

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        left = [height[0]] * n
        right = [height[-1]] * n
        for i in range(1, n):
            left[i] = max(left[i - 1], height[i])
            right[n - i - 1] = max(right[n - i], height[n - i - 1])
        return sum(min(l, r) - h for l, r, h in zip(left, right, height))

Continue Practicing

#85 maximal rectangle #321 create maximum number #581 shortest unsorted continuous subarray