LeetCode 42 Trapping Rain Water - Why Naive Fails

For each position, find the maximum height to its left and right. Water at that position is min(leftMax, rightMax) - height[i].

Finding the maximum on each side takes $O(n)$ per position. With $n$ positions, that's $O(n^2)$ total.

For $n = 2 \times 10^4$, you'd have $4 \times 10^8$ operations. Too slow.