Trapping Rain Water Problem in DSA C

Mental Model

Imagine bars of different heights and water trapped between them after rain. We want to find how much water stays trapped without spilling.

Analogy: Think of a row of buildings with different heights after rain. Water collects in the dips between taller buildings, like puddles trapped between walls.

Height bars: 3 0 2 0 4
Visual: 3 ↑   
         |   
         |   2 ↑
         |   |   
         |   |   4 ↑
Water trapped between bars fills the dips.

Dry Run Walkthrough

Input: height array: [3, 0, 2, 0, 4]

Goal: Calculate total units of water trapped between bars after rain

Step 1: Calculate max height to the left of each bar

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

Why: We need to know the tallest bar on the left to know water limit

Step 2: Calculate max height to the right of each bar

right_max = [4, 4, 4, 4, 4]

Why: We need tallest bar on the right to know water limit

Step 3: Calculate trapped water at each bar by min(left_max, right_max) - height

water trapped per bar = [0, 3, 1, 3, 0]

Why: Water level is limited by shorter side, subtract bar height to get trapped water

Step 4: Sum trapped water at all bars

total water = 0 + 3 + 1 + 3 + 0 = 7

Why: Total trapped water is sum of water trapped at each position

Result:

Final trapped water: 7 units

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

int trap(int* height, int heightSize) {
    if (heightSize == 0) return 0;
    int *left_max = (int*)malloc(heightSize * sizeof(int));
    int *right_max = (int*)malloc(heightSize * sizeof(int));
    int water = 0;

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

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

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

    free(left_max);
    free(right_max);
    return water;
}

int main() {
    int height[] = {3, 0, 2, 0, 4};
    int size = sizeof(height) / sizeof(height[0]);
    int result = trap(height, size);
    printf("Total trapped water: %d\n", result);
    return 0;
}

left_max[0] = height[0];

initialize left max with first bar height

for (int i = 1; i < heightSize; i++) { if (height[i] > left_max[i - 1]) left_max[i] = height[i]; else left_max[i] = left_max[i - 1]; }

build left max array by tracking tallest bar from left

right_max[heightSize - 1] = height[heightSize - 1];

initialize right max with last bar height

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

build right max array by tracking tallest bar from right

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

calculate trapped water at each bar by min of left and right max minus bar height

Output

Total trapped water: 7

Complexity Analysis

Time: O(n) because we traverse the height array three times linearly

Space: O(n) because we use two extra arrays to store left and right max heights

vs Alternative: Compared to brute force O(n^2) checking each bar's left and right max on the fly, this approach is much faster

Edge Cases

empty height array

returns 0 as no bars means no trapped water

DSA C

if (heightSize == 0) return 0;

all bars same height

returns 0 as no dips to trap water

DSA C

water += min_height - height[i]; // results in zero for flat bars

strictly increasing or decreasing bars

returns 0 as water cannot be trapped on slopes

DSA C

water += min_height - height[i]; // no positive trapped water

When to Use This Pattern

When you see a problem asking how much water is trapped between bars or heights, use the trapping rain water pattern with left and right max arrays to find water limits efficiently.

Common Mistakes

Mistake: Calculating trapped water using only left max or only right max
Fix: Use the minimum of left max and right max heights at each position to correctly find water level

Mistake: Not handling empty input array
Fix: Add a guard clause to return 0 if input size is zero

Mistake: Forgetting to free allocated memory for left_max and right_max arrays
Fix: Call free() on both arrays before returning result

Summary

Calculates total water trapped between bars after rain using left and right max heights.

Use when you need to find how much water can be trapped between uneven heights efficiently.

The key insight is water level at each bar is limited by the shorter tallest bar on either side.

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