Problem

Table: Heights

1
2
3
4
5
6
7
8

+-------------+------+
| 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 inany order.

The result format is in the following example.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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.

Solution

Method 1 – Prefix Max and Suffix Max Aggregation

Intuition

To calculate trapped rainwater, for each bar, the water above it is determined by the minimum of the maximum heights to its left and right, minus its own height. In SQL, we can use window functions to compute prefix and suffix maximums for each bar.

Approach

  1. For each row, compute:
    • left_max: the maximum height from the start up to the current bar (inclusive).
    • right_max: the maximum height from the current bar to the end (inclusive).
  2. For each bar, calculate the trapped water as GREATEST(LEAST(left_max, right_max) - height, 0).
  3. Sum the trapped water for all bars to get the total.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

WITH left_right_max AS (
  SELECT
    id,
    height,
    MAX(height) OVER (ORDER BY id ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS left_max,
    MAX(height) OVER (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING) AS right_max
  FROM Heights
)
SELECT SUM(GREATEST(LEAST(left_max, right_max) - height, 0)) AS total_trapped_water
FROM left_right_max;

Complexity

  • ⏰ Time complexity: O(n) — n is the number of bars (single scan with window functions).
  • 🧺 Space complexity: O(n) — For window function buffers.