Trapping Rain Water - LeetCode Solution in C++, Java, Python

1. Introduction

The "Trapping Rain Water" problem involves computing the total amount of water that can be trapped between the bars in a histogram-like elevation map. This problem tests understanding of arrays and the concept of computing volumes between boundaries.

2. Problem

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

3. Solution in C++

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

    vector<int> leftMax(n), rightMax(n);
    leftMax[0] = height[0];
    for (int i = 1; i < n; i++)
        leftMax[i] = max(height[i], leftMax[i - 1]);

    rightMax[n - 1] = height[n - 1];
    for (int i = n - 2; i >= 0; i--)
        rightMax[i] = max(height[i], rightMax[i + 1]);

    int trappedWater = 0;
    for (int i = 0; i < n; i++)
        trappedWater += min(leftMax[i], rightMax[i]) - height[i];

    return trappedWater;
}

Explanation:

1. Calculate the maximum height to the left and right of each bar using two arrays leftMax and rightMax.

2. The amount of water each bar can trap is the minimum of its left and right maximum heights minus its own height.

3. Sum up the trapped water for each bar to get the total amount.

4. Solution in Java

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

    int[] leftMax = new int[n];
    int[] rightMax = new int[n];
    leftMax[0] = height[0];
    for (int i = 1; i < n; i++)
        leftMax[i] = Math.max(height[i], leftMax[i - 1]);

    rightMax[n - 1] = height[n - 1];
    for (int i = n - 2; i >= 0; i--)
        rightMax[i] = Math.max(height[i], rightMax[i + 1]);

    int trappedWater = 0;
    for (int i = 0; i < n; i++)
        trappedWater += Math.min(leftMax[i], rightMax[i]) - height[i];

    return trappedWater;
}

Explanation:

1. Compute the left and right maximum heights for each bar in arrays leftMax and rightMax.

2. The water trapped at each bar is determined by the minimum of the left and right maximum heights minus the bar's height.

3. The total trapped water is the sum of water trapped at each bar.

5. Solution in Python

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

    n = len(height)
    leftMax, rightMax = [0] * n, [0] * n
    leftMax[0] = height[0]
    for i in range(1, n):
        leftMax[i] = max(height[i], leftMax[i - 1])

    rightMax[n - 1] = height[n - 1]
    for i in range(n - 2, -1, -1):
        rightMax[i] = max(height[i], rightMax[i + 1])

    return sum(min(leftMax[i], rightMax[i]) - height[i] for i in range(n))

Explanation:

1. Initialize leftMax and rightMax lists to store the maximum height to the left and right of each bar.

2. Iterate over height to fill in leftMax and rightMax.

3. Calculate the water trapped at each bar as the minimum of its left and right max heights minus its height.

4. Sum the trapped water at each bar to get the total amount.