Trapping Rain Water In C,CPP,JAVA,PYTHON,C#,JS

/ DSA / By
Spread the love
Close-up of HTML code highlighted in vibrant colors on a computer monitor.

The Trapping Rain Water problem asks us to compute how much water can be trapped between bars of varying heights after it rains. The problem typically provides an array where each element represents the height of a bar, and we need to calculate how much water can be stored between these bars.

Problem Statement:

Given an array height[] representing the height of bars in a histogram, the task is to compute the amount of water that can be trapped between the bars after raining.

Example:

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The total water trapped is 6 units.

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9

Approach:

To solve this problem efficiently, we can use the two-pointer technique combined with precomputed maximum heights. Here’s a breakdown of the approach:

  1. Two-pointer technique:
    • Use two pointers: one (left) starting at the beginning of the array, and the other (right) starting at the end.
    • Move the pointers towards each other while calculating the trapped water.
    • At each step, compare the height at left and right. The idea is to ensure we always process the lower height since the amount of trapped water depends on the height of the shorter bar.
  2. Tracking Maximum Heights:
    • Keep track of the maximum height encountered so far from the left (left_max) and from the right (right_max).
    • If height[left] is less than or equal to height[right], calculate the water trapped at the left pointer.
      • If the height at left is greater than or equal to left_max, update left_max.
      • If the height at left is less than left_max, compute the trapped water as left_max - height[left] and add it to the result.
    • If height[right] is greater than height[left], calculate the water trapped at the right pointer similarly.
      • If the height at right is greater than or equal to right_max, update right_max.
      • If the height at right is less than right_max, compute the trapped water as right_max - height[right] and add it to the result.
  3. Result:
    • Sum the trapped water calculated at each step, and return the result.

Time Complexity:

  • Time Complexity: O(n), where n is the number of elements in the height array. We are iterating through the array only once.
  • Space Complexity: O(1), as we are using a constant amount of extra space.

Code Implementations:

1. C:

#include <stdio.h>

int trap(int* height, int heightSize) {
    if (heightSize == 0) return 0;
    
    int left = 0, right = heightSize - 1;
    int left_max = 0, right_max = 0;
    int water_trapped = 0;
    
    while (left <= right) {
        if (height[left] <= height[right]) {
            if (height[left] >= left_max) {
                left_max = height[left];
            } else {
                water_trapped += left_max - height[left];
            }
            left++;
        } else {
            if (height[right] >= right_max) {
                right_max = height[right];
            } else {
                water_trapped += right_max - height[right];
            }
            right--;
        }
    }
    
    return water_trapped;
}

int main() {
    int height[] = {0,1,0,2,1,0,1,3,2,1,2,1};
    int size = sizeof(height) / sizeof(height[0]);
    printf("Trapped Water: %d\n", trap(height, size));
    return 0;
}

2. C++:

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

int trap(vector<int>& height) {
    int n = height.size();
    if (n == 0) return 0;

    int left = 0, right = n - 1;
    int left_max = 0, right_max = 0;
    int water_trapped = 0;

    while (left <= right) {
        if (height[left] <= height[right]) {
            if (height[left] >= left_max) {
                left_max = height[left];
            } else {
                water_trapped += left_max - height[left];
            }
            left++;
        } else {
            if (height[right] >= right_max) {
                right_max = height[right];
            } else {
                water_trapped += right_max - height[right];
            }
            right--;
        }
    }

    return water_trapped;
}

int main() {
    vector<int> height = {0,1,0,2,1,0,1,3,2,1,2,1};
    cout << "Trapped Water: " << trap(height) << endl;
    return 0;
}

3. Java:

public class Solution {
    public int trap(int[] height) {
        int n = height.length;
        if (n == 0) return 0;

        int left = 0, right = n - 1;
        int leftMax = 0, rightMax = 0;
        int waterTrapped = 0;

        while (left <= right) {
            if (height[left] <= height[right]) {
                if (height[left] >= leftMax) {
                    leftMax = height[left];
                } else {
                    waterTrapped += leftMax - height[left];
                }
                left++;
            } else {
                if (height[right] >= rightMax) {
                    rightMax = height[right];
                } else {
                    waterTrapped += rightMax - height[right];
                }
                right--;
            }
        }

        return waterTrapped;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
        System.out.println("Trapped Water: " + solution.trap(height));
    }
}

4. Python:

def trap(height):
    if not height:
        return 0

    left, right = 0, len(height) - 1
    left_max, right_max = 0, 0
    water_trapped = 0

    while left <= right:
        if height[left] <= height[right]:
            if height[left] >= left_max:
                left_max = height[left]
            else:
                water_trapped += left_max - height[left]
            left += 1
        else:
            if height[right] >= right_max:
                right_max = height[right]
            else:
                water_trapped += right_max - height[right]
            right -= 1

    return water_trapped

# Example usage
height = [0,1,0,2,1,0,1,3,2,1,2,1]
print(f"Trapped Water: {trap(height)}")

5. C#:

using System;

public class Solution {
    public int Trap(int[] height) {
        int n = height.Length;
        if (n == 0) return 0;

        int left = 0, right = n - 1;
        int leftMax = 0, rightMax = 0;
        int waterTrapped = 0;

        while (left <= right) {
            if (height[left] <= height[right]) {
                if (height[left] >= leftMax) {
                    leftMax = height[left];
                } else {
                    waterTrapped += leftMax - height[left];
                }
                left++;
            } else {
                if (height[right] >= rightMax) {
                    rightMax = height[right];
                } else {
                    waterTrapped += rightMax - height[right];
                }
                right--;
            }
        }

        return waterTrapped;
    }

    public static void Main(string[] args) {
        Solution solution = new Solution();
        int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
        Console.WriteLine("Trapped Water: " + solution.Trap(height));
    }
}

6. JavaScript:

var trap = function(height) {
    let n = height.length;
    if (n === 0) return 0;

    let left = 0, right = n - 1;
    let leftMax = 0, rightMax = 0;
    let waterTrapped = 0;

    while (left <= right) {
        if (height[left] <= height[right]) {
            if (height[left] >= leftMax) {
                leftMax = height[left];
            } else {
                waterTrapped += leftMax - height[left];
            }
            left++;
        } else {
            if (height[right] >= rightMax) {
                rightMax = height[right];
            } else {
                waterTrapped += rightMax - height[right];
            }
            right--;
        }
    }

    return waterTrapped;
};

// Example usage
const height = [0,1,0,2,1,0,1,3,2,1,2,1];
console.log("Trapped Water: ", trap(height));

Summary:

  • Time Complexity: O(n), where n is the number of elements in the array height.
  • Space Complexity: O(1), since we use only a few extra variables for pointers and maximum heights.