Trapping Rain Water Problem in DSA C - Build from Scratch

Trapping Rain Water Problem

📖 Scenario: Imagine you have a row of walls with different heights. When it rains, water gets trapped between these walls. You want to find out how much water is trapped after the rain stops.

🎯 Goal: Build a program that calculates the total amount of water trapped between walls represented by an array of heights.

📋 What You'll Learn

Create an array called height with exact values representing wall heights

Create two arrays called left_max and right_max to store maximum heights from left and right

Calculate trapped water using the height, left_max, and right_max arrays

Print the total trapped water as an integer

💡 Why This Matters

🌍 Real World

This problem models how water collects in valleys between walls or buildings, useful in civil engineering and flood management.

💼 Career

Understanding this algorithm helps in software roles involving simulation, game development, and problem-solving skills.

1

Create the height array

Create an integer array called height with these exact values: 0,1,0,2,1,0,1,3,2,1,2,1. Also create an integer variable n and set it to the length of the array, which is 12.

DSA C

# Create the height array and its length
// Your code here

Hint

Use int height[12] = { ... }; to create the array and int n = 12; for its size.

2

Create left_max and right_max arrays

Create two integer arrays called left_max and right_max, each of size n. These will store the maximum wall height to the left and right of each position.

DSA C

#include 

int main() {
    int height[12] = {0,1,0,2,1,0,1,3,2,1,2,1};
    int n = 12;

    // Create left_max and right_max arrays
    // Your code here

    return 0;
}

Hint

Declare arrays with int left_max[12]; and int right_max[12];.

3

Calculate left_max, right_max and trapped water

Fill the left_max array so each element is the maximum height from the left up to that index. Fill the right_max array so each element is the maximum height from the right up to that index. Then, create an integer variable water set to 0. Use a for loop with variable i from 0 to n-1 to calculate trapped water at each position by adding (left_max[i] < right_max[i] ? left_max[i] : right_max[i]) - height[i] to water.

DSA C

#include 

int main() {
    int height[12] = {0,1,0,2,1,0,1,3,2,1,2,1};
    int n = 12;
    int left_max[12];
    int right_max[12];

    // Calculate left_max
    // Your code here

    // Calculate right_max
    // Your code here

    // Calculate trapped water
    // Your code here

    return 0;
}

Hint

Use loops to fill left_max and right_max. Then sum trapped water using the minimum of these two arrays minus the height.

4

Print the total trapped water

Print the integer variable water using printf to display the total trapped water.

DSA C

#include 

int main() {
    int height[12] = {0,1,0,2,1,0,1,3,2,1,2,1};
    int n = 12;
    int left_max[12];
    int right_max[12];

    left_max[0] = height[0];
    for (int i = 1; i  left_max[i-1]) ? height[i] : left_max[i-1];
    }

    right_max[n-1] = height[n-1];
    for (int i = n - 2; i >= 0; i--) {
        right_max[i] = (height[i] > right_max[i+1]) ? height[i] : right_max[i+1];
    }

    int water = 0;
    for (int i = 0; i < n; i++) {
        int min_height = (left_max[i] < right_max[i]) ? left_max[i] : right_max[i];
        water += min_height - height[i];
    }

    // Print the total trapped water
    // Your code here

    return 0;
}

Hint

Use printf("%d\n", water); to print the total trapped water.