Trapping Rain Water Problem

Problem Description

Given an array height representing the height of blocks, calculate how much water can be trapped after rainfall. Water can only be trapped between blocks if there is a taller block on both the left and the right of the current block.

---

Objective

Find the total amount of water that can be trapped between the blocks.

---

Key Insight

For each block, the water it can trap is determined by:
min(leftMax, rightMax) - height[i]
Where:

• leftMax is the maximum height of blocks to the left of the current block.
• rightMax is the maximum height of blocks to the right of the current block.

---

Approach

1. Calculate Left Maximum Heights:

• Traverse the array of blocks from left to right.
• Track the maximum height encountered so far for each block and store it in a new array leftMax.

2. Calculate Right Maximum Heights:

• Traverse the array of blocks from right to left.
• Track the maximum height encountered so far for each block and store it in another array rightMax.

3. Calculate Water at Each Block:

• Traverse the array of blocks.
• For each block:
  • Compute the trapped water at index i as:
    water[i] = min(leftMax[i], rightMax[i]) - height[i]
  • Add this value to the total trapped water.

4. Return Total Water Trapped:

• After the traversal, return the sum of all trapped water.

---

Example

Input:

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

Left Maximum Heights:

[0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3]

Right Maximum Heights:

[3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1]

Water Trapped at Each Block:

[0, 0, 1, 0, 1, 2, 1, 0, 0, 1, 0, 0]

Total Trapped Water:

6

Output:
6

---

Test Cases

Test Case 1

Input:
height = [4, 2, 0, 3, 2, 5]

Output:
9

Explanation:
Water trapped at each block: [0, 2, 4, 1, 2, 0]
Total water trapped = 9.

---

Test Case 2

Input:
height = [1, 0, 2]

Output:
1

Explanation:
Water trapped at each block: [0, 1, 0]
Total water trapped = 1.

---

Test Case 3

Input:
height = [0, 1, 0, 1, 0]

Output:
0

Explanation:
No water is trapped because no block has taller blocks on both sides.

---

Test Case 4

Input:
height = [3, 0, 0, 2, 0, 4]

Output:
10

Explanation:
Water trapped at each block: [0, 3, 3, 1, 3, 0]
Total water trapped = 10.

---

Constraints

1. 1 <= height.length <= 10^5
2. 0 <= height[i] <= 10^4

---

Complexity

Time Complexity:

• O(n): Single pass for calculating leftMax, rightMax, and total water trapped.

Space Complexity:

• O(n): Space used for leftMax and rightMax arrays.

For an optimized version, we can reduce space complexity to O(1) using two-pointer technique.

— Written by Saurabh Patil • B.Tech CSE • Software Developer