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.