Trapping Rain Water - C Solution

1. Introduction

This blog post discusses a popular problem in computational geometry and array manipulation - "Trapping Rain Water". The challenge is to calculate the amount of water that can be trapped between bars of varying heights, a scenario that can be visualized as water being trapped between buildings during rainfall. This problem is an excellent way to understand the application of array data structures in solving real-world geometric problems.

Problem

Given n non-negative integers representing an elevation map where each bar has a width of 1 unit, the task is to compute the total amount of water that can be trapped after raining.

2. Solution Steps

1. Initialize two arrays, leftMax and rightMax, to store the highest bar height to the left and right of each bar.

2. Iterate from left to right, filling leftMax with the maximum height encountered so far.

3. Similarly, iterate from right to left, filling rightMax.

4. Iterate through each bar and calculate the water that can be trapped using the formula min(leftMax[i], rightMax[i]) - height[i].

5. Sum these values to get the total trapped water.

3. Code Program

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

// Function to calculate the total trapped rain water
int trap(int* height, int heightSize) {
    if (heightSize == 0) return 0;

    int* leftMax = (int*)malloc(sizeof(int) * heightSize);
    int* rightMax = (int*)malloc(sizeof(int) * heightSize);
    int trappedWater = 0;

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

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

    // Calculate trapped water for each bar
    for (int i = 0; i < heightSize; i++) {
        trappedWater += (leftMax[i] < rightMax[i] ? leftMax[i] : rightMax[i]) - height[i];
    }

    free(leftMax);
    free(rightMax);
    return trappedWater;
}

// Main function to test the trap function
int main() {
    int heights1[] = {0,1,0,2,1,0,1,3,2,1,2,1};
    printf("Trapped Rain Water (Example 1): %d\n", trap(heights1, 12));

    int heights2[] = {4,2,0,3,2,5};
    printf("Trapped Rain Water (Example 2): %d\n", trap(heights2, 6));

    return 0;
}

Output:

Trapped Rain Water (Example 1): 6
Trapped Rain Water (Example 2): 9

Explanation:

1. Allocate memory for leftMax and rightMax arrays.

2. Fill leftMax with the maximum height to the left of each bar.

3. Fill rightMax with the maximum height to the right of each bar.

4. For each bar, calculate the water that can be trapped above it.

5. Sum these values to get the total trapped water.

6. Free the allocated memory.

7. The main function tests the trap function with two examples and prints the total trapped rainwater.