LeetCode Problem 3061

Difficulty: 🔴 Hard
Topics: Database

Solution

LeetCode 3061 - Calculate Trapping Rain Water

Problem Understanding

This problem asks us to compute how much rainwater can be trapped between vertical bars after rainfall. The bars are represented in a database table named Heights, where each row contains an id and a height. The id values are sequential, which means they define the left-to-right order of the bars in the landscape.

Each bar has a width of exactly 1, so the only thing that matters is the height of each position. Water can accumulate in valleys between taller bars. The amount of water above a specific position depends on the tallest bar to its left and the tallest bar to its right.

More formally, for every position:

• The water level is limited by the shorter of:

• the maximum height on the left

• the maximum height on the right

• The trapped water at that position is:

$$\text{water} = \min(\text{leftMax}, \text{rightMax}) - \text{height}$$

If this value is negative, the trapped water is 0.

The goal is to return a single row containing the total amount of trapped rainwater across all positions.

The input represents an elevation map. Each row corresponds to a vertical bar. The expected output is one integer representing the total trapped water.

The problem guarantees that:

• id values are unique and sequential
• Heights are non-negative integers
• Bars appear in left-to-right order according to id

These guarantees simplify the implementation because we do not need to sort or handle missing positions.

Several edge cases are important:

• A strictly increasing landscape traps no water.
• A strictly decreasing landscape also traps no water.
• Very short arrays, such as one or two bars, cannot trap water.
• Flat terrain traps no water.
• Deep valleys between tall bars may trap large amounts of water.
• Multiple separated valleys must all be counted correctly.

A naive implementation can easily become inefficient because calculating left and right maximums repeatedly for every bar leads to quadratic complexity.

Approaches

Brute Force Approach

The brute-force solution evaluates every bar independently.

For each position:

1. Scan leftward to find the tallest bar on the left.
2. Scan rightward to find the tallest bar on the right.
3. Compute the water level using the smaller of those two heights.
4. Add the trapped water for that position to the answer.

This approach is correct because the amount of water above any bar is completely determined by the tallest barriers on both sides.

However, the problem is inefficiency. If there are n bars, and for every bar we scan the entire left and right portions of the array, the total work becomes:

$$O(n^2)$$

This becomes too slow for large inputs.

Optimal Approach

The key insight is that we do not need to repeatedly recompute left and right maximum heights.

Instead, we can preprocess:

• left_max[i], the tallest bar from the beginning up to index i
• right_max[i], the tallest bar from the end down to index i

Once these arrays are available, the trapped water at every position can be computed in constant time.

This transforms the repeated scanning into a linear-time solution.

Another optimal solution uses two pointers with constant extra space, but the prefix/suffix maximum approach is often easier to understand and implement clearly in SQL-style reasoning problems.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Recomputes left and right maximums for every bar
Optimal	O(n)	O(n)	Precomputes prefix and suffix maximum arrays

Algorithm Walkthrough

Optimal Prefix/Suffix Maximum Algorithm

1. Store all heights in an array in left-to-right order.

The order matters because trapped water depends on neighboring bars. 2. Create a left_max array.

For each position i, store the tallest height seen from the left up to index i.

Example:

heights   = [0,1,0,2]
left_max  = [0,1,1,2]

3. Create a right_max array.

For each position i, store the tallest height seen from the right up to index i.

Example:

heights    = [0,1,0,2]
right_max  = [2,2,2,2]

4. Iterate through every position.

At each index:

• The highest possible water level is limited by the shorter boundary.
• Compute:

$$\min(left_max[i], right_max[i]) - height[i]$$ 5. Add the trapped water to the total.

Only positive values contribute water. 6. Return the final accumulated total.

Why it works

Water above a position can only rise as high as the shorter wall surrounding it. Even if one side has an extremely tall barrier, water would spill over the shorter side first.

The left_max array guarantees we know the tallest barrier on the left, and the right_max array guarantees we know the tallest barrier on the right. Therefore, the minimum of these two values gives the exact maximum water level at each position.

Subtracting the current height gives the trapped water at that bar.

Because this logic is independently correct for every index, summing all positions produces the total trapped water.

Python Solution

from typing import List

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)

        if n < 3:
            return 0

        left_max = [0] * n
        right_max = [0] * n

        left_max[0] = height[0]
        for i in range(1, n):
            left_max[i] = max(left_max[i - 1], height[i])

        right_max[n - 1] = height[n - 1]
        for i in range(n - 2, -1, -1):
            right_max[i] = max(right_max[i + 1], height[i])

        total_water = 0

        for i in range(n):
            water_level = min(left_max[i], right_max[i])
            total_water += water_level - height[i]

        return total_water

The implementation begins by handling small inputs. Fewer than three bars cannot trap water because there are not enough boundaries to form a container.

Next, the algorithm builds the left_max array. Each position stores the tallest bar encountered so far while scanning from left to right.

The right_max array is then built in reverse order. Each position stores the tallest bar encountered so far while scanning from right to left.

Once both arrays are available, the algorithm computes the trapped water at every index. The effective water level is the smaller of the two boundaries because water spills over the shorter side first.

Finally, the trapped water values are accumulated and returned.

Go Solution

package main

func trap(height []int) int {
	n := len(height)

	if n < 3 {
		return 0
	}

	leftMax := make([]int, n)
	rightMax := make([]int, n)

	leftMax[0] = height[0]
	for i := 1; i < n; i++ {
		leftMax[i] = max(leftMax[i-1], height[i])
	}

	rightMax[n-1] = height[n-1]
	for i := n - 2; i >= 0; i-- {
		rightMax[i] = max(rightMax[i+1], height[i])
	}

	totalWater := 0

	for i := 0; i < n; i++ {
		waterLevel := min(leftMax[i], rightMax[i])
		totalWater += waterLevel - height[i]
	}

	return totalWater
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

The Go implementation follows the exact same logic as the Python version.

Slices are used instead of Python lists. Since Go does not provide built-in min and max helpers for integers, separate helper functions are implemented.

The algorithm uses integer arithmetic throughout, so overflow is not a concern under normal LeetCode constraints.

Worked Examples

Example 1

height = [0,1,0,2,1,0,1,3,2,1,2,1]

Step 1: Build left_max

Index	Height	left_max
0	0	0
1	1	1
2	0	1
3	2	2
4	1	2
5	0	2
6	1	2
7	3	3
8	2	3
9	1	3
10	2	3
11	1	3

Result:

left_max = [0,1,1,2,2,2,2,3,3,3,3,3]

Step 2: Build right_max

Index	Height	right_max
11	1	1
10	2	2
9	1	2
8	2	2
7	3	3
6	1	3
5	0	3
4	1	3
3	2	3
2	0	3
1	1	3
0	0	3

Result:

right_max = [3,3,3,3,3,3,3,3,2,2,2,1]

Step 3: Compute trapped water

Index	Height	left_max	right_max	Water Level	Trapped
0	0	0	3	0	0
1	1	1	3	1	0
2	0	1	3	1	1
3	2	2	3	2	0
4	1	2	3	2	1
5	0	2	3	2	2
6	1	2	3	2	1
7	3	3	3	3	0
8	2	3	2	2	0
9	1	3	2	2	1
10	2	3	2	2	0
11	1	3	1	1	0

Total trapped water:

1 + 1 + 2 + 1 + 1 = 6

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each array is traversed a constant number of times
Space	O(n)	Two auxiliary arrays store prefix and suffix maximums

The algorithm performs three linear passes:

1. Build left_max
2. Build right_max
3. Compute trapped water

Each pass touches every element once, so the total runtime is linear.

The extra space comes from storing two arrays of size n.

Test Cases

sol = Solution()

# Provided example
assert sol.trap([0,1,0,2,1,0,1,3,2,1,2,1]) == 6  # standard trapping example

# Empty input
assert sol.trap([]) == 0  # no bars

# Single bar
assert sol.trap([5]) == 0  # cannot trap water

# Two bars
assert sol.trap([5,3]) == 0  # insufficient boundaries

# Strictly increasing
assert sol.trap([1,2,3,4,5]) == 0  # water runs off right side

# Strictly decreasing
assert sol.trap([5,4,3,2,1]) == 0  # water runs off left side

# Flat terrain
assert sol.trap([3,3,3,3]) == 0  # no valleys

# Simple valley
assert sol.trap([3,0,3]) == 3  # single trapped region

# Deep valley
assert sol.trap([5,0,0,0,5]) == 15  # multiple trapped units

# Multiple valleys
assert sol.trap([4,2,0,3,2,5]) == 9  # several trapping regions

# Alternating peaks
assert sol.trap([2,0,2,0,2]) == 4  # repeated valleys

# Large plateau inside boundaries
assert sol.trap([5,1,1,1,5]) == 12  # flat trapped region

# All zeros
assert sol.trap([0,0,0,0]) == 0  # no walls

# High center bar
assert sol.trap([5,0,5,0,5]) == 10  # separate valleys

Test Case Summary

Test	Why
[0,1,0,2,1,0,1,3,2,1,2,1]	Standard reference example
[]	Empty input handling
[5]	Single-element boundary case
[5,3]	Two bars cannot trap water
[1,2,3,4,5]	Strictly increasing heights
[5,4,3,2,1]	Strictly decreasing heights
[3,3,3,3]	Flat terrain
[3,0,3]	Smallest non-trivial trapped region
[5,0,0,0,5]	Deep wide valley
[4,2,0,3,2,5]	Multiple trapping regions
[2,0,2,0,2]	Alternating valleys
[5,1,1,1,5]	Plateau inside boundaries
[0,0,0,0]	All-zero heights
[5,0,5,0,5]	Multiple isolated basins

Edge Cases

Very Small Inputs

Arrays with fewer than three bars cannot trap water because at least two boundaries and one interior position are required. This case is easy to overlook, especially when indexing into prefix or suffix arrays. The implementation handles this immediately with:

if n < 3:
    return 0

This prevents invalid indexing and unnecessary computation.

Monotonic Height Sequences

Strictly increasing or strictly decreasing landscapes trap no water because there is never a valley enclosed by taller bars on both sides.

Naive implementations sometimes incorrectly accumulate negative values or assume every interior position traps something. In this implementation, the water level is always computed using:

min(left_max[i], right_max[i]) - height[i]

Since the minimum boundary equals the current height in monotonic sequences, trapped water becomes zero naturally.

Large Flat Regions

Flat regions inside tall boundaries can trap substantial water across many positions. For example:

[5,1,1,1,5]

traps 4 units above each middle position.

Some incorrect implementations only count local minima rather than considering the entire bounded region. The prefix/suffix maximum method evaluates every position independently, ensuring all trapped units are counted correctly.