Practice/Bloomberg/Leetcode 42. Trapping Rain Water

Leetcode 42. Trapping Rain Water

CodingMust

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.