LeetCode 3061: Calculate Trapping Rain Water Solution

Master LeetCode problem 3061 (Calculate Trapping Rain Water), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

3061. Calculate Trapping Rain Water

Hard

Database

Problem Explanation

Explanation:

To solve the "Calculate Trapping Rain Water" problem, we can use a two-pointer approach. We will iterate over the array from left to right and from right to left, keeping track of the maximum height encountered so far from the left and right sides for each position. We will then calculate the amount of water trapped at each position by taking the minimum of the maximum heights from both sides minus the height at the current position.

Steps:

Initialize left and right pointers at the start and end of the array, respectively, and variables to keep track of the maximum height from left and right sides.
Iterate over the array while the left pointer is less than the right pointer.
Update the maximum height from the left side if the height at the left pointer is greater.
Update the maximum height from the right side if the height at the right pointer is greater.
Calculate the trapped water at the current position using the formula mentioned above.
Move the pointer with the smaller height towards the center.
Repeat steps 3-6 until the left pointer crosses the right pointer.
Return the total trapped water.

Time Complexity: O(n) - where n is the number of elements in the input array. Space Complexity: O(1) - constant space is used.

Solution Code

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

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 3061 (Calculate Trapping Rain Water)?

This page provides optimized solutions for LeetCode problem 3061 (Calculate Trapping Rain Water) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 3061 (Calculate Trapping Rain Water)?

The time complexity for LeetCode 3061 (Calculate Trapping Rain Water) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 3061 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 3061 in Java, C++, or Python.

Back to LeetCode Solutions