Trapping Rain Water 🌧️🏠

Welcome to our comprehensive lesson on Trapping Rain Water! This concept is a key algorithmic problem in the field of Computer Science, especially in Data Structures and Algorithms. We'll dive deep into understanding this problem, its real-world applications, and how to solve it using code.

What is Trapping Rain Water? 💡

Imagine a series of buildings of different heights forming a row. During a heavy rain, rainwater accumulates between the buildings. The objective is to maximize the amount of water that can be collected in rooftop tanks by altering the height of the buildings.

Buildings Row

Real-world Applications 📝

This problem has numerous practical applications, such as:

Irrigation systems: Maximizing water collection in dry regions can help ensure adequate water supply.
Flood control: Understanding the flow of water in urban areas can help in designing efficient drainage systems.

Understanding the Solution 🎯

Our goal is to build a function that calculates the maximum amount of water that can be collected in rooftop tanks. Here's a step-by-step breakdown of the approach:

Iterate through the array, and for each index i, find the minimum height from the left and right of the current building.
Calculate the water level for the current building as the minimum height between the left and right, minus the height of the current building.
Multiply the water level by the width (assumed 1 for simplicity) to get the water capacity for the current building.
Add the water capacity to a running total, which will eventually hold the maximum amount of water that can be collected.

Implementation ✅

Let's dive into some code examples to bring this all together:

Example 1 - Python

python

def max_water(heights):
    if not heights:
        return 0

    max_water = 0
    left, right = 0, len(heights) - 1

    while left < right:
        water_level = min(heights[left], heights[right]) * (right - left)

        if water_level > max_water:
            max_water = water_level

        if heights[left] < heights[right]:
            left += 1
        else:
            right -= 1

    return max_water

Example 2 - Java

java

public int maxWater(int[] heights) {
    if (heights == null || heights.length == 0) {
        return 0;
    }

    int maxWater = 0;
    int left = 0, right = heights.length - 1;

    while (left < right) {
        int waterLevel = Math.min(heights[left], heights[right]) * (right - left);

        if (waterLevel > maxWater) {
            maxWater = waterLevel;
        }

        if (heights[left] < heights[right]) {
            left++;
        } else {
            right--;
        }
    }

    return maxWater;
}

💡 Pro Tip: Remember to handle edge cases, such as empty arrays or arrays with a single element.

Quiz 🎲

That's it for our comprehensive lesson on Trapping Rain Water! We hope you've enjoyed learning this fascinating problem and its real-world applications. Happy coding! 🎉👋