Why Trapping Rain Water Problem in DSA C?

The Big Idea

Discover how a clever trick turns a messy water problem into a simple calculation!

The Scenario

Imagine you have a row of uneven walls after a rainstorm, and you want to know how much water is trapped between them. Trying to measure each gap by hand is like guessing how much water each dip can hold without a clear method.

The Problem

Manually calculating trapped water by checking each wall and its neighbors is slow and confusing. It's easy to miss spots or double count water, especially when walls vary in height. This leads to mistakes and wasted time.

The Solution

The Trapping Rain Water Problem uses a smart approach to quickly find how much water each wall can hold by looking at the tallest walls on its left and right. This method avoids guesswork and gives the answer efficiently.

Before vs After

✗ Before

int totalWater = 0;
for (int i = 1; i < n - 1; i++) {
  int leftMax = 0, rightMax = 0;
  for (int j = 0; j <= i; j++) leftMax = max(leftMax, height[j]);
  for (int j = i; j < n; j++) rightMax = max(rightMax, height[j]);
  totalWater += min(leftMax, rightMax) - height[i];
}

✓ After

int left = 0, right = n - 1;
int leftMax = 0, rightMax = 0;
int totalWater = 0;
while (left < right) {
  if (height[left] < height[right]) {
    if (height[left] >= leftMax) leftMax = height[left];
    else totalWater += leftMax - height[left];
    left++;
  } else {
    if (height[right] >= rightMax) rightMax = height[right];
    else totalWater += rightMax - height[right];
    right--;
  }
}

What It Enables

This problem's solution lets you quickly find trapped water in any uneven surface, helping in real-world tasks like flood prediction and landscape design.

Real Life Example

After heavy rain, city planners use this method to estimate how much water will collect between buildings or hills, helping prevent floods and design better drainage.

Key Takeaways

Manual checking is slow and error-prone.

Using tallest walls on each side speeds up calculation.

Efficient solution helps in real-world water management.