Skip to main content
Talentd

Calculate Trapping Rain Water - Solution & Explanation

HardPremiumFree on FleetCodeDatabase4 min read
Practice this problem

Problem Statement

Table: Heights

+-------------+------+
| Column Name | Type |
+-------------+------+
| id          | int  |
| height      | int  |
+-------------+------+
id is the primary key (column with unique values) for this table, and it is guaranteed to be in sequential order.
Each row of this table contains an id and height.

Write a solution to calculate the amount of rainwater can be trapped between the bars in the landscape, considering that each bar has a width of 1 unit.

Return the result table in any order.

The result format is in the following example.

 

Example 1:

Input: 
Heights table:
+-----+--------+
| id  | height |
+-----+--------+
| 1   | 0      |
| 2   | 1      |
| 3   | 0      |
| 4   | 2      |
| 5   | 1      |
| 6   | 0      |
| 7   | 1      |
| 8   | 3      |
| 9   | 2      |
| 10  | 1      |
| 11  | 2      |
| 12  | 1      |
+-----+--------+
Output: 
+---------------------+
| total_trapped_water | 
+---------------------+
| 6                   | 
+---------------------+
Explanation: 


The elevation map depicted above (in the black section) is graphically represented with the x-axis denoting the id and the y-axis representing the heights [0,1,0,2,1,0,1,3,2,1,2,1]. In this scenario, 6 units of rainwater are trapped within the blue section.

Approach Overview

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.

Solution

We use the window function MAX(height) OVER (ORDER BY id) to calculate the maximum height for each position and its left side, and use MAX(height) OVER (ORDER BY id DESC) to calculate the maximum height for each position and its right side, denoted as l and r respectively. Then, the amount of water stored at each position is min(l, r) - height. Finally, we sum them up.

Code

MySQLPython

MySQL

Python

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Self Join Range AggregationO(n²)O(1)Conceptual baseline or when demonstrating the raw definition of left and right boundaries
Prefix & Suffix Maximums via SubqueriesO(n)O(n)When window functions are unavailable but derived tables or scans are acceptable
Window Function + SummationO(n)O(n)Best modern SQL solution; efficient for large datasets using analytic window operations

Video Solution

Trapping Rain Water - Google Interview Question - Leetcode 42 • NeetCode • 558,064 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Calculate Trapping Rain Water easy or hard?
Calculate Trapping Rain Water is generally considered a hard problem because it requires recognizing the boundary constraint that determines trapped water. Efficient solutions depend on computing left and right maximums or using a two‑pointer optimization to achieve O(n) time.
Calculate Trapping Rain Water Python/Java solution
In Python or Java array versions, you typically compute left_max and right_max arrays or use a two‑pointer technique scanning from both ends. For database variants, Python solutions often use SQL execution or dataframe-style window operations to replicate the same prefix maximum logic.
How to solve Calculate Trapping Rain Water in O(n)?
Compute two running maximum values for every row: the tallest bar to the left and the tallest bar to the right. In SQL, use window functions like MAX(height) OVER ordered windows to generate these values. The trapped water at each index is min(left_max, right_max) minus the current height, and summing all rows produces the final answer.
What is the best approach for Calculate Trapping Rain Water?
The best approach uses SQL window functions to compute running maximum heights from both directions. Each row calculates left_max and right_max using MAX() OVER window clauses, then applies min(left_max, right_max) - height to determine trapped water. This solution runs in O(n) time with O(n) auxiliary columns and avoids repeated scans.
Is Calculate Trapping Rain Water asked at Google/Amazon/Meta?
Variants of the trapping rain water problem frequently appear in interviews at companies such as Google, Amazon, and Meta. The array version tests two‑pointer and prefix maximum reasoning, while database versions evaluate SQL window function skills and analytical queries.
What data structure is used in Calculate Trapping Rain Water?
The logic relies on prefix and suffix maximum arrays conceptually. In SQL implementations, these are produced using window function columns rather than explicit arrays. The calculation is essentially range maximum queries combined with aggregation.
What is the time complexity of Calculate Trapping Rain Water?
The optimal implementation runs in O(n) time because each row is processed once while computing prefix and suffix maximums using window functions. Less optimized SQL approaches using joins or repeated scans can degrade to O(n²) time.

Ready to solve this problem?

Practice Calculate Trapping Rain Water with our built-in code editor and test cases.

Practice on FleetCode
Previous

Combine Two Tables

Next

Second Highest Salary