Solution For Trapping Rain Water

The Trapping Rain Water problem on LeetCode asks us to find the amount of water that can be trapped given a list of heights. Here’s a step-by-step solution:

1. First, we need to identify the maximum height in the list. We’ll call this max_height.

2. Create two pointers, left and right, at the beginning and end of the list respectively.

3. Create two variables, left_max and right_max, both initialized to 0.

4. Create a variable, water, initialized to 0.

5. While left is less than or equal to right:

a. If the height at the left pointer is less than or equal to the height at the right pointer:

i. If the height at the left pointer is greater than left_max, set left_max to the height at the left pointer.

ii. Otherwise, add left_max minus the height at the left pointer to the water variable, and move the left pointer to the right.

b. If the height at the left pointer is greater than the height at the right pointer:

i. If the height at the right pointer is greater than right_max, set right_max to the height at the right pointer.

ii. Otherwise, add right_max minus the height at the right pointer to the water variable, and move the right pointer to the left.

1. After the while loop, return the value of water.

Here’s the Python code implementation:

“`
def trap(height):
max_height = max(height)
left = 0
right = len(height) – 1
left_max = right_max = water = 0

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

return water

“`

Step by Step Implementation For Trapping Rain Water

public class Solution {
    public int trap(int[] height) {
        int left = 0, right = height.length - 1;
        int ans = 0;
        int left_max = 0, right_max = 0;
        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] >= left_max) {
                    left_max = height[left];
                } else {
                    ans += (left_max - height[left]);
                }
                ++left;
            }
            else {
                if (height[right] >= right_max) {
                    right_max = height[right];
                } else {
                    ans += (right_max - height[right]);
                }
                --right;
            }
        }
        return ans;
    }
}

def trap(height):
    
    # initialize left and right pointers
    left = 0
    right = len(height) - 1
    
    # initialize max left and max right
    max_left = 0
    max_right = 0
    
    # initialize water trapped
    water = 0
    
    while left < right:
        if height[left] < height[right]:
            # update max left if necessary
            if height[left] > max_left:
                max_left = height[left]
            # water is equal to the difference between the current element and the max left
            else:
                water += max_left - height[left]
            # move left pointer up
            left += 1
        else:
            # update max right if necessary
            if height[right] > max_right:
                max_right = height[right]
            # water is equal to the difference between the current element and the max right
            else:
                water += max_right - height[right]
            # move right pointer down
            right -= 1
            
    return water

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    // initialize output
    let output = 0;
    
    // edge case: empty or single-element input
    if (height.length < 2) {
        return output;
    }
    
    // initialize pointers
    let left = 0;
    let right = height.length - 1;
    
    // initialize max heights
    let leftMax = height[left];
    let rightMax = height[right];
    
    // while left pointer is less than right pointer
    while (left < right) {
        // if left max height is less than right max height
        if (leftMax < rightMax) {
            // update output with difference between current height and left max height
            output += Math.max(0, leftMax - height[left]);
            // update left max height if current height is greater
            leftMax = Math.max(leftMax, height[left]);
            // move left pointer
            left++;
        }
        // otherwise
        else {
            // update output with difference between current height and right max height
            output += Math.max(0, rightMax - height[right]);
            // update right max height if current height is greater
            rightMax = Math.max(rightMax, height[right]);
            // move right pointer
            right--;
        }
    }
    
    // return output
    return output;
};

class Solution {
public:
    int trap(vector& height) {
        int left = 0, right = height.size() - 1;
        int ans = 0;
        int left_max = 0, right_max = 0;
        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] >= left_max) {
                    left_max = height[left];
                }
                else {
                    ans += (left_max - height[left]);
                }
                ++left;
            }
            else {
                if (height[right] >= right_max) {
                    right_max = height[right];
                }
                else {
                    ans += (right_max - height[right]);
                }
                --right;
            }
        }
        return ans;
    }
};

public class Solution {
    public int Trap(int[] height) {
        int n = height.Length;
        int[] left = new int[n];
        int[] right = new int[n];
        int water = 0;
        left[0] = height[0];
        for (int i = 1; i < n; i++) {
            left[i] = Math.Max(left[i-1], height[i]);
        }
        right[n-1] = height[n-1];
        for (int i = n-2; i >= 0; i--) {
            right[i] = Math.Max(right[i+1], height[i]);
        }
        for (int i = 0; i < n; i++) {
            water += Math.Min(left[i], right[i]) - height[i];
        }
        return water;
    }
}