Table of contents

Trapping Rain Water

Given an array where each element represents the height of a bar in a histogram, calculate how much water would be trapped between the bars after it rains. The width of each bar is 1.

Input/Output Examples

plaintext
Example 1:
Input:
arr = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
Output: 6
Explanation: The array represents an elevation map where the water trapped between the bars is 6 units.

Example 2:
Input:
arr = [4, 2, 0, 3, 2, 5]
Output: 9
Explanation: The water trapped between the bars is 9 units.

Approach to implement Trapping Rain Water

  1. Two-Pointer Technique:
    • Use two pointers, left and right, starting from the leftmost and rightmost positions of the array. Track the maximum heights encountered from both directions using left_max and right_max.
  2. Calculate Trapped Water:
    • While left is less than right, compare arr[left] and arr[right]:
      • If arr[left] is less than arr[right], check if arr[left] is greater than left_max. If it is, update left_max; otherwise, add the difference between left_max and arr[left] to the trapped water. Increment the left pointer.
      • If arr[right] is less than or equal to arr[left], check if arr[right] is greater than right_max. If it is, update right_max; otherwise, add the difference between right_max and arr[right] to the trapped water. Decrement the right pointer.
  3. Continue Until Pointers Meet:
    • Repeat the above process until the left and right pointers meet. The trapped water will be accumulated in a variable.

C++ Program to implement Trapping Rain Water

cpp
#include <iostream>
#include <vector>
using namespace std;

// Function to calculate the total trapped rainwater
int trapRainWater(vector<int>& arr) {
    int left = 0, right = arr.size() - 1;
    int left_max = 0, right_max = 0;
    int water_trapped = 0;

    // Traverse the elevation map with two pointers
    while (left < right) {
        if (arr[left] < arr[right]) {
            // If the current height is greater than the left maximum, update it
            if (arr[left] >= left_max) {
                left_max = arr[left];
            } else {
                // Otherwise, add the trapped water at the current position
                water_trapped += left_max - arr[left];
            }
            left++;
        } else {
            // If the current height is greater than the right maximum, update it
            if (arr[right] >= right_max) {
                right_max = arr[right];
            } else {
                // Otherwise, add the trapped water at the current position
                water_trapped += right_max - arr[right];
            }
            right--;
        }
    }

    return water_trapped;
}

int main() {
    vector<int> arr = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
    int result = trapRainWater(arr);
    cout << "Total water trapped: " << result << " units" << endl;
    return 0;
}

Java Program to implement Trapping Rain Water

java
public class TrappingRainWater {

    // Function to calculate the total trapped rainwater
    public static int trapRainWater(int[] arr) {
        int left = 0, right = arr.length - 1;
        int left_max = 0, right_max = 0;
        int water_trapped = 0;

        // Traverse the elevation map with two pointers
        while (left < right) {
            if (arr[left] < arr[right]) {
                // If the current height is greater than the left maximum, update it
                if (arr[left] >= left_max) {
                    left_max = arr[left];
                } else {
                    // Otherwise, add the trapped water at the current position
                    water_trapped += left_max - arr[left];
                }
                left++;
            } else {
                // If the current height is greater than the right maximum, update it
                if (arr[right] >= right_max) {
                    right_max = arr[right];
                } else {
                    // Otherwise, add the trapped water at the current position
                    water_trapped += right_max - arr[right];
                }
                right--;
            }
        }

        return water_trapped;
    }

    public static void main(String[] args) {
        int[] arr = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        int result = trapRainWater(arr);
        System.out.println("Total water trapped: " + result + " units");
    }
}

Python Program to implement Trapping Rain Water

python
# Function to calculate the total trapped rainwater
def trap_rain_water(arr):
    left, right = 0, len(arr) - 1
    left_max, right_max = 0, 0
    water_trapped = 0

    # Traverse the elevation map with two pointers
    while left < right:
        if arr[left] < arr[right]:
            # If the current height is greater than the left maximum, update it
            if arr[left] >= left_max:
                left_max = arr[left]
            else:
                # Otherwise, add the trapped water at the current position
                water_trapped += left_max - arr[left]
            left += 1
        else:
            # If the current height is greater than the right maximum, update it
            if arr[right] >= right_max:
                right_max = arr[right]
            else:
                # Otherwise, add the trapped water at the current position
                water_trapped += right_max - arr[right]
            right -= 1

    return water_trapped

# Example usage
if __name__ == "__main__":
    arr = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
    result = trap_rain_water(arr)
    print("Total water trapped:", result, "units")

Time Complexity:

  • O(n): Each element of the array is processed once.

Space Complexity:

  • O(1): The algorithm uses a constant amount of extra space.

DSA

Related Articles