Practice/Apple/Leetcode 3061. Calculate Trapping Rain Water

Leetcode 3061. Calculate Trapping Rain Water

CodingMust

Problem

You are given an array representing the heights of vertical walls positioned at equal intervals. After a rainstorm, water becomes trapped between these walls. Your task is to calculate the total volume of water that can be held.

Water accumulates at any position when there are taller walls on both its left and right sides. The amount of water at each position is determined by the height difference between the water level (limited by the shorter of the two surrounding peaks) and the wall at that position.

Requirements

1. Return the total units of water that can be trapped between the walls
2. Handle edge cases where no water can be trapped (ascending, descending, or insufficient walls)
3. Treat each position as having a width of 1 unit
4. Water cannot be trapped at the first or last position

Constraints

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

Examples

Example 1:

` Input: heights = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] Output: 6 Explanation: The elevation map forms valleys where water accumulates:

• At index 2: water level is min(1, 2) = 1, trapped = 1 - 0 = 1
• At index 4: water level is min(2, 3) = 2, trapped = 2 - 1 = 1
• At index 5: water level is min(2, 3) = 2, trapped = 2 - 0 = 2
• At index 6: water level is min(2, 3) = 2, trapped = 2 - 1 = 1
• At index 9: water level is min(3, 2) = 2, trapped = 2 - 1 = 1 Total: 1 + 1 + 2 + 1 + 1 = 6 `

Example 2:

` Input: heights = [4, 2, 0, 3, 2, 5] Output: 9 Explanation:

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

Example 3:

Input: heights = [3, 2, 1] Output: 0 Explanation: No water can be trapped in a descending sequence