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.

Practice

1. What does the Trapping Rain Water problem aim to find given an array of heights?

easy

A. The minimum height of the bars

B. The maximum height of the bars

C. The number of bars in the array

D. The total amount of water trapped between the bars after raining

Solution

1. Step 1: Understand the problem context

   The problem involves an array representing heights of bars where water can be trapped between them.

2. Step 2: Identify the goal

   The goal is to calculate how much water can be trapped after raining between these bars.

3. Final Answer:

   The total amount of water trapped between the bars after raining -> Option D

4. Quick Check:

   Trapping Rain Water = Total trapped water [OK]

Hint: Think of bars as walls holding water in between [OK]

Common Mistakes:

• Confusing trapped water with bar heights
• Calculating max or min height instead of trapped water
• Ignoring the space between bars

2. Which of the following C code snippets correctly declares an array to store bar heights for the Trapping Rain Water problem?

easy

A. int heights[] = {4, 2, 0, 3, 2, 5};

B. int heights = {4, 2, 0, 3, 2, 5};

C. int heights[6] = (4, 2, 0, 3, 2, 5);

D. int heights[6] = [4, 2, 0, 3, 2, 5];

Solution

1. Step 1: Check array declaration syntax in C

   Arrays are declared with type, name, and initializer list in braces {}.

2. Step 2: Validate each option

   int heights[] = {4, 2, 0, 3, 2, 5}; uses correct syntax: int heights[] = {4, 2, 0, 3, 2, 5}; Options A, B, D have syntax errors.

3. Final Answer:

   int heights[] = {4, 2, 0, 3, 2, 5}; -> Option A

4. Quick Check:

   Correct C array syntax = int heights[] = {4, 2, 0, 3, 2, 5}; [OK]

Hint: Use braces {} to initialize arrays in C [OK]

Common Mistakes:

• Using parentheses () instead of braces {}
• Missing array size or incorrect initializer syntax
• Using square brackets [] for initialization

3. What is the output of the following C code snippet that calculates trapped water?

int heights[] = {3, 0, 2, 0, 4};
int n = 5;
int left_max[5], right_max[5];
int water = 0;

// Calculate left max
left_max[0] = heights[0];
for (int i = 1; i < n; i++) {
    left_max[i] = (heights[i] > left_max[i-1]) ? heights[i] : left_max[i-1];
}

// Calculate right max
right_max[n-1] = heights[n-1];
for (int i = n-2; i >= 0; i--) {
    right_max[i] = (heights[i] > right_max[i+1]) ? heights[i] : right_max[i+1];
}

// Calculate trapped water
for (int i = 0; i < n; i++) {
    water += (left_max[i] < right_max[i] ? left_max[i] : right_max[i]) - heights[i];
}

printf("%d\n", water);

medium

A. 4

B. 6

C. 7

D. 5

Solution

1. Step 1: Calculate left_max and right_max arrays

   left_max = [3, 3, 3, 3, 4], right_max = [4, 4, 4, 4, 4]

2. Step 2: Calculate trapped water at each index

   Water trapped = sum of min(left_max[i], right_max[i]) - heights[i] = (3-3)+(3-0)+(3-2)+(3-0)+(4-4) = 0+3+1+3+0 = 7

3. Final Answer:

   7 -> Option C

4. Quick Check:

   Sum trapped water = 7 [OK]

Hint: Use left_max and right_max arrays to find trapped water fast [OK]

Common Mistakes:

• Mixing up left_max and right_max arrays
• Forgetting to subtract heights from min of max arrays
• Off-by-one errors in loops

4. Identify the bug in this C code snippet for calculating trapped rain water:

int trap(int* height, int heightSize) {
    int left_max[heightSize];
    int right_max[heightSize];
    int water = 0;

    left_max[0] = height[0];
    for (int i = 1; i < heightSize; i++) {
        left_max[i] = height[i] > left_max[i-1] ? height[i] : left_max[i-1];
    }

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

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

    return water;
}

medium

A. Incorrect comparison operator in left_max calculation

B. Using variable length arrays (VLA) which may not be supported

C. Wrong loop range in right_max calculation

D. Missing initialization of water variable

Solution

1. Step 1: Analyze array declarations

   The code uses int left_max[heightSize]; and int right_max[heightSize]; which are variable length arrays (VLA).

2. Step 2: Understand VLA support in C

   VLAs are optional in C11 and may not be supported by all compilers, causing portability issues or errors.

3. Final Answer:

   Using variable length arrays (VLA) which may not be supported -> Option B

4. Quick Check:

   VLAs may cause errors = Using variable length arrays (VLA) which may not be supported [OK]

Hint: Avoid VLAs; use dynamic memory or fixed size arrays [OK]

Common Mistakes:

• Assuming VLAs always work in all C compilers
• Ignoring compiler warnings about VLAs
• Confusing VLA issue with logic errors

5. Given the heights array {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}, what is the total trapped rain water using the two-pointer approach in C?

hard

A. 6

B. 5

C. 7

D. 8

Solution

1. Step 1: Understand two-pointer approach

   Use two pointers left and right starting at ends, track left_max and right_max, move pointers inward calculating trapped water.

2. Step 2: Dry run the array

   Heights: [0,1,0,2,1,0,1,3,2,1,2,1] Water trapped = 6 units after calculating min(left_max, right_max) - height at each step.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Two-pointer trapped water = 6 [OK]

Hint: Use two pointers and track max heights from both ends [OK]

Common Mistakes:

• Not updating left_max and right_max correctly
• Moving pointers incorrectly causing missed water
• Confusing two-pointer with prefix arrays method