Calculate Trapping Rain Water - Video Solutions

Problem Overview: You receive elevation heights representing bars in order. Water can be trapped between taller bars on the left and right. The task is to compute the total amount of water trapped after rainfall using database-style operations.

Approach 1: Prefix & Suffix Maximums via Subqueries (O(n) time, O(n) space)

The trapped water at position i depends on the tallest bar to its left and right. If you know left_max[i] and right_max[i], the water above that bar is min(left_max, right_max) - height. In SQL, you can compute these values using correlated subqueries or derived tables that scan earlier and later rows. After computing both maxima, iterate through the rows and sum the valid trapped water values. This approach mirrors the classic array solution but implemented with SQL scans, which increases query cost on large datasets.

Approach 2: Self Join Range Aggregation (O(n²) time, O(1) extra space)

A more brute-force SQL strategy joins each row with all rows to its left and right to compute the maximum height in those ranges. For each index, aggregate MAX(height) from rows with smaller positions and from rows with larger positions. Then calculate trapped water with the same min(left_max, right_max) - height formula and sum the results. This method is easy to reason about but expensive because every row performs range scans through joins.

Approach 3: Window Function + Summation (O(n) time, O(n) space)

The most efficient SQL solution uses window functions. Compute the running maximum from the left using MAX(height) OVER (ORDER BY id ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW). Compute the right-side maximum using a reversed window order. These window columns give left_max and right_max for every row in a single pass. The trapped water per row becomes GREATEST(LEAST(left_max, right_max) - height, 0), and a final SUM() aggregates the result. This approach leverages modern database optimizations and avoids repeated scans, making it the preferred production query pattern.

Recommended for interviews: Start by explaining the classic prefix/suffix maximum idea to demonstrate the underlying algorithm. Then translate that logic into SQL using window functions. Interviewers expect the O(n) reasoning because it shows you understand the water trapping constraint: water at each position depends only on the highest boundaries on both sides.