Trapping Rain Water

Ready

Elevation Map

Left Max (lmax)

Right Max (rmax)

Operation: -

Current Phase

Current Index (i)

Left Max

Right Max

Total Water

Click "Step" or "Play" to start the visualization

Elevation

Current Index

Left Max

Right Max

Trapped Water

Final Result

Python Code
                n = len(height)
            
                lmax = [0] * n
            
                rmax = [0] * n
            
                lmax[0] = height[0]
            
                rmax[n-1] = height[n-1]
            
                for i in range(1, n):
            
                    lmax[i] = max(lmax[i-1], height[i])
            
                for i in range(n-2, -1, -1):
            
                    rmax[i] = max(rmax[i+1], height[i])
            
                out = 0
            
                for i in range(n):
            
                    out += min(lmax[i], rmax[i]) - height[i]
            
                return out

Complexity Analysis

Time Complexity O(n) Space Complexity O(n)

Time Complexity: O(n)

Breakdown

Pass 1 (left max): iterate indices 1 to n-1, one comparison per index
Pass 2 (right max): iterate indices n-2 down to 0, one comparison per index
Pass 3 (water calculation): iterate all n indices, one min and one subtraction per index
Total operations: (n-1) + (n-1) + n = 3n - 2

T(n) = 3n - 2 = O(n)

Mathematical Intuition

For each position i, water trapped equals min(leftMax, rightMax) - height[i]. Computing left max and right max from scratch per index costs O(n) each, totaling O(n²). Precomputing them in separate passes reduces this to O(n) with three independent linear scans.

Key Insight

Water level at any position is bounded by the shorter of the tallest walls on either side. Precomputing these boundaries avoids redundant scans.

Space Complexity: O(n)

Breakdown

lmax: array of n elements storing left maximums
rmax: array of n elements storing right maximums
out: single integer accumulator
Loop variable i: single integer

S(n) = 2n + O(1) = O(n)

Mathematical Intuition

Two auxiliary arrays of size n store the running maximums from each direction. A two-pointer approach can reduce space to O(1) by computing left and right max on the fly, but the array approach is clearer for visualization and understanding.

Key Insight

The space trade-off is between O(n) with precomputed arrays (simpler logic) and O(1) with two pointers (more complex but space-efficient). Both achieve O(n) time.