Calculate Trapping Rain Water - Problem

Given a table Heights containing id and height columns, calculate the amount of rainwater that can be trapped between the bars in the landscape. Each bar has a width of 1 unit.

Problem: For each position, water can be trapped if there are taller bars on both sides. The water level at any position is determined by the minimum of the maximum heights to its left and right, minus the current height.

Table Structure:

  • id: Sequential position identifier (primary key)
  • height: Height of the bar at that position

Return the total amount of trapped rainwater as a single value.

Table Schema

Heights
Column Name Type Description
id PK int Sequential position identifier (primary key)
height int Height of the bar at that position
Primary Key: id
Note: id values are guaranteed to be in sequential order representing positions in the landscape

Input & Output

Example 1 — Basic Rain Water Trapping
Input Table:
id height
1 0
2 1
3 0
4 2
5 1
6 0
7 1
8 3
Output:
trapped_water
6
💡 Note:

Water gets trapped at positions where there are higher bars on both sides. Position 3 (height=0) traps 1 unit between bars at positions 2 and 4. Position 5 (height=1) traps 1 unit, and position 6 (height=0) traps 1 unit. Additional water is trapped at other positions, totaling 6 units.
Example 2 — No Water Trapped
Input Table:
id height
1 3
2 2
3 1
4 0
Output:
trapped_water
0
💡 Note:

This is a decreasing sequence of heights, so no water can be trapped. Water would flow off to the right side, resulting in 0 trapped water.
Example 3 — Single Valley
Input Table:
id height
1 3
2 0
3 2
Output:
trapped_water
2
💡 Note:

Position 2 has height 0 and is surrounded by heights 3 and 2. The water level is min(3,2) = 2, so 2 units of water are trapped at position 2.

Constraints

  • 1 ≤ number of rows ≤ 20000
  • 0 ≤ height ≤ 35000
  • id values are sequential and start from 1

Visualization

Tap to expand
Rain Water Trapping Problem OverviewHeights Tableidheight10213042Visual Representation0102Water trapped in valleysSQLCalculationResulttrapped_water1Algorithm: MIN(left_max, right_max) - heightPosition 3: min(1,2) - 0 = 1 unit trapped
Understanding the Visualization
1
Heights
Input bar heights at each position
2
Analysis
Calculate left/right maximums
3
Water
Sum trapped water amounts
Key Takeaway
🎯 Key Insight: Use window functions to efficiently calculate the maximum heights on both sides of each position, then determine trapped water levels

Related Problems

Asked in
Amazon 28 Microsoft 22 Google 19
28.5K Views
Medium Frequency
~25 min Avg. Time
892 Likes
Ln 1, Col 1
Smart Actions
💡 Explanation
AI Ready
💡 Suggestion Tab to accept Esc to dismiss
// Output will appear here after running code
Code Editor Closed
Click the red button to reopen