Leetcode 42. Trapping Rain Water

Problem

You are given an array representing the elevation profile of a terrain, where each element corresponds to a vertical bar of width 1 positioned consecutively. After rainfall, water will accumulate in the valleys between these bars.

Your task is to calculate the total volume of water that can be trapped between the bars. Water at any position is bounded by the tallest bar to its left and the tallest bar to its right. The water level at a position equals the minimum of these two bounding heights, minus the bar's own height at that position.

Requirements

1. Return the total number of units of water that can be trapped
2. Each bar has a width of 1 unit
3. Water cannot be trapped at the edges (first and last positions)
4. Handle edge cases including empty arrays and arrays with fewer than 3 elements

Constraints

• 0 ≤ heights.length ≤ 20,000
• 0 ≤ heights[i] ≤ 100,000
• Aim for O(n) time complexity and O(1) or O(n) space complexity

Examples

Example 1:

` Input: heights = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] Output: 6 Explanation: The bars form multiple valleys. Water accumulates as follows:

• At index 2: min(1, 2) - 0 = 1 unit
• At index 4: min(2, 3) - 1 = 1 unit
• At index 5: min(2, 3) - 0 = 2 units
• At index 6: min(2, 3) - 1 = 1 unit
• At index 9: min(3, 2) - 1 = 1 unit Total: 6 units `

Example 2:

` Input: heights = [4, 2, 0, 3, 2, 5] Output: 9 Explanation: A large valley forms between the first bar (height 4) and last bar (height 5).

• At index 1: min(4, 5) - 2 = 2 units
• At index 2: min(4, 5) - 0 = 4 units
• At index 3: min(4, 5) - 3 = 1 unit
• At index 4: min(4, 5) - 2 = 2 units Total: 9 units `

Example 3:

Input: heights = [3, 0, 2] Output: 2 Explanation: Water fills the valley at index 1 up to height 2.

Hint 1: Think About Water Level For each position, the water level is determined by the minimum of the maximum heights to its left and right. The trapped water at that position is this water level minus the bar's height (if positive).

Hint 2: Pre-compute Boundaries Consider pre-computing the maximum height to the left and right of each position. This allows you to calculate trapped water in a single pass through the array.

Hint 3: Two-Pointer Optimization You can solve this problem with O(1) extra space using two pointers starting from both ends. Move the pointer with the smaller maximum height inward while accumulating water based on the current maximum at that side.

Full Solution `` Approach Explanation:

The two-pointer solution works by maintaining two pointers at the start and end of the array, along with the maximum heights seen from each side.

Key Insight: At any moment, if heights[left] < heights[right], we know that the water trapped at position left is determined solely by left_max (not right_max), because there exists a taller bar on the right (at least heights[right]).

Algorithm Steps:

1. Initialize two pointers at array boundaries and track maximum heights from each side
2. Always process the pointer with the smaller current height
3. If current height exceeds the respective max, update the max (no water trapped)
4. Otherwise, add the difference between max and current height to total water
5. Move the processed pointer inward and repeat

Time Complexity: O(n) - We visit each element exactly once

Space Complexity: O(1) - Only a constant number of variables used

Alternative Approach (Dynamic Programming):

You could also solve this using two auxiliary arrays to pre-compute left_max[i] and right_max[i] for each position, then calculate water in a final pass. This uses O(n) space but is conceptually simpler.

` def trapWaterDP(heights): """Alternative O(n) space solution using pre-computed arrays.""" if not heights: return 0

n = len(heights)
left_max = [0] * n
right_max = [0] * n

# Fill left_max array
left_max[0] = heights[0]
for i in range(1, n):
    left_max[i] = max(left_max[i-1], heights[i])

# Fill right_max array
right_max[n-1] = heights[n-1]
for i in range(n-2, -1, -1):
    right_max[i] = max(right_max[i+1], heights[i])

# Calculate trapped water
total_water = 0
for i in range(n):
    water_level = min(left_max[i], right_max[i])
    total_water += max(0, water_level - heights[i])

return total_water

`