Trapping Rain Water

For each index i, scan left to find the tallest bar so far and scan right to find the tallest bar from there on, then apply the formula. It’s correct because it computes leftMax[i] and rightMax[i] exactly as defined, but it re-scans large chunks of the array for every single index.

class Solution:
    def trap(self, height: list[int]) -> int:
        n = len(height)
        water = 0
        for i in range(n):
            left_max = max(height[:i + 1])
            right_max = max(height[i:])
            water += min(left_max, right_max) - height[i]
        return water

Why it’s slow: left_max and right_max are recomputed with a fresh O(n) scan at every index, giving O(n²) time total, even though most of that scanning is redundant — leftMax[i] and leftMax[i-1] differ by at most one comparison.

Precompute leftMax[i] (the tallest bar in height[0..i]) and rightMax[i] (the tallest bar in height[i..n-1]) in two linear passes, building each on top of the previous value instead of rescanning. Then a single pass applies the same min(leftMax[i], rightMax[i]) - height[i] formula.

class Solution:
    def trap(self, height: list[int]) -> int:
        n = len(height)
        if n == 0:
            return 0
        left_max = [0] * n
        right_max = [0] * n
        left_max[0] = height[0]
        for i in range(1, n):
            left_max[i] = max(left_max[i - 1], height[i])
        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])
        return sum(min(left_max[i], right_max[i]) - height[i] for i in range(n))

Complexity: three linear passes (left-to-right, right-to-left, and the final sum) → O(n) time. Storing both max arrays costs O(n) space — an improvement in time over brute force, but not in space.

The suffix array is only ever used to answer “is the wall on my right at least as tall as the wall on my left?” — we don’t need its exact values everywhere, just enough to know which side is the binding constraint at each step. Track leftMax and rightMax as running maxima behind two pointers closing in from either end. Whichever side currently has the shorter running max is the side we can safely resolve: its true rightMax (or leftMax) doesn’t matter yet, because the other side is already tall enough to trap whatever this side can hold.

class Solution:
    def trap(self, height: list[int]) -> int:
        l, r = 0, len(height) - 1
        left_max = right_max = 0
        water = 0
        while l < r:
            if height[l] < height[r]:
                if height[l] >= left_max:
                    left_max = height[l]
                else:
                    water += left_max - height[l]
                l += 1
            else:
                if height[r] >= right_max:
                    right_max = height[r]
                else:
                    water += right_max - height[r]
                r -= 1
        return water

Tracing height = [4, 2, 0, 3, 2, 5] (expected 9). Since height[5] = 5 is the tallest bar in the array, every comparison below takes the left branch — rightMax is never touched, which is fine, since the algorithm only needs to know it’s at least height[r], and that’s already guaranteed by height[l] < height[r]:

Correctness: whenever height[l] < height[r], the true rightMax at this point must be >= height[r] (since height[r] itself hasn’t been surpassed yet), and height[r] > height[l]. So rightMax > height[l] is guaranteed without ever computing it exactly — leftMax alone determines how much water sits above index l. The symmetric argument holds when height[r] <= height[l]. Every index is resolved exactly once by whichever pointer reaches it, so no position is double-counted or skipped.

Complexity: l and r each advance one step per iteration and the loop ends when they meet, so every index is visited once → O(n) time. Only a handful of scalar variables are kept — no arrays — so it’s O(1) space, matching the best possible for this problem.