Introduction

The Trapping Rain Water problem involves calculating how much water can be trapped between bars after rainfall.

Given:

  • array of heights

Each bar:

  • width = 1

The task is to:

  • calculate total trapped water

Water trapped at index depends on:

 minimum(leftMax,rightMax) - currentHeight

This problem is one of the most important applications of:

Two Pointers + Monotonic Concepts

This problem helps in understanding:

  • prefix maximums
  • suffix maximums
  • two pointer optimization
  • area calculations

Example

Input:height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output:
6

Explanation:
Total trapped water:
6 units

Constraints

1 <= height.length <= 2 * 10^40 <= height[i] <= 10^5

Approach 1 : Brute Force Traversal

Explanation

The simplest way is:

  1. For every bar:
    • find tallest left bar
    • find tallest right bar
  2. Water trapped:
 min(leftMax, rightMax) - height[i]
This works but repeated searching becomes inefficient.

Steps

  1. Traverse every index.
  2. Find maximum left height.
  3. Find maximum right height.
  4. Calculate trapped water.
  5. Add total water.

Dry Run

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

Index 2:
Left Max = 4
Right Max = 5

Water:
min(4,5) - 0 = 4

Total trapped water:
9

Brute Force Code

Complexity Analysis

Time Complexity: O(n²)Explanation:
Left and right maximums are repeatedly searched.

Space Complexity: O(1)
Explanation:
No extra arrays are used.

Approach 2 : Two Pointer Optimization

Explanation

The optimized solution uses:

 Two Pointers

Idea:

  • maintain:
    • left pointer
    • right pointer
  • track:
    • leftMax
    • rightMax

Key Observation:

  • smaller side determines water level

Process:

  1. Compare leftMax and rightMax
  2. Move smaller side inward
  3. Calculate trapped water

This avoids repeated traversal.

Steps

  1. Initialize two pointers.
  2. Maintain leftMax and rightMax.
  3. Move smaller side.
  4. Calculate trapped water.
  5. Return total water.

Dry Run

Input:[4,2,0,3,2,5]
Left = 0
Right = 5
leftMax = 4
rightMax = 5

Move left:
Water at index 1:
4 - 2 = 2

Water at index 2:
4 - 0 = 4

Continue...

Total Water:
9

Two Pointer Code

Complexity Analysis

Time Complexity: O(n)Explanation:
Each index is processed once.

Space Complexity: O(1)
Explanation:
Only constant variables are used.

Edge Cases

  1. Empty array
  2. Strictly increasing heights
  3. Strictly decreasing heights
  4. Flat surface
  5. Single bar

Why This Problem is Important

Trapping Rain Water helps in understanding:

  1. Two pointer optimization
  2. Prefix/suffix maximum concepts
  3. Area calculations
  4. Efficient traversal
  5. Water trapping logic

It is one of the most important advanced array interview problems.

Real-World Applications

Water trapping concepts are used in:

  1. Terrain analysis
  2. Flood prediction systems
  3. Graphics simulations
  4. Construction planning
  5. Elevation mapping

Common Mistakes

  1. Incorrect pointer movement
  2. Wrong water calculation
  3. Forgetting max updates
  4. Using larger side incorrectly

Interview Tips

Interviewers often expect:

  1. Two pointer explanation
  2. Water trapping reasoning
  3. Prefix/suffix logic understanding

Always explain:

  • why smaller side determines water
  • how leftMax/rightMax work
  • why traversal becomes linear

Related Questions

  1. Largest Rectangle in Histogram
  2. Container With Most Water
  3. Daily Temperatures
  4. Next Greater Element
  5. Sum of Subarray Minimums

Final Takeaway

The Trapping Rain Water problem is a fundamental advanced array and monotonic concept problem that teaches efficient water calculation and two-pointer optimization techniques. Understanding this problem builds a strong foundation for advanced stack, array, and geometry-based interview problems.