42. Trapping Rain Water (Round 2)

Trapping Rain Water problem on LeetCode (Hard) Given an array height representing an elevation map where each bar has width 1, return how much rain water can be trapped after raining. The key idea is that water above each index depends on the tallest wall to its left and the tallest wall to its right. The water level is limited by the shorter wall: min(leftMax, rightMax) - height[i]. Brute Force Solution: Time Complexity: O(n²) Space Complexity: O(1) Prefix/Suffix Max Solution: Time Complexity: O(n) Space Complexity: O(n) Optimized Two Pointer Solution: Time Complexity: O(n) Space Complexity: O(1) The brute force solution recalculates the tallest left and right walls for every index. The prefix/suffix max solution avoids repeated scanning by precomputing leftMax and rightMax arrays first, then calculating water at each index in one final pass. The two-pointer solution improves space by keeping only leftMax and rightMax variables instead of full arrays.