Trapping Rain Water LeetCode Solution

Last updated on January 20th, 2025 at 04:07 am

Here, we see the Trapping Rain Water LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Array, Dynamic Programming, Stack, Two-Pointers

Companies

Amazon, Apple, Bloomberg, Google, Twitter, Zenefits

Level of Question

Hard

Trapping Rain Water LeetCode Solution

Trapping Rain Water LeetCode Solution

1. Problem Statement

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.

Trapping Rain Water leetcode ex1
fig-1
Example 1: (fig-1)
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.
Example 2:
Input: height = [4,2,0,3,2,5]
Output: 9

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is Two Pointers. This pattern is commonly used to solve problems involving arrays or lists where two pointers traverse the data structure from different directions to achieve the desired result. In this case, the problem involves calculating the amount of trapped rainwater, and the two pointers are used to efficiently compute the water trapped between the heights.

3. Code Implementation in Different Languages

3.1 Trapping Rain Water C++

class Solution {
public:
    int trap(vector<int>& height) {
        if (!height.size()) return 0;
        int len = height.size(), dp[len], currMax = -1, res = 0;
        for (int i = 0, e; i < len; i++) {
            e = height[i];
            currMax = max(currMax, e);
            dp[i] = currMax - e;
        }
        currMax = -1;
        for (int i = len - 1, e; i > -1; i--) {
            e = height[i];
            currMax = max(currMax, e);
            res += min(dp[i], currMax - e);
        }
        return res;        
    }
};

3.2 Trapping Rain Water Java

class Solution {
    public int trap(int[] height) {
        int l = 0, r = height.length - 1, sum = 0, lMax = 0, rMax = 0;
        while(l <= r){
            lMax = Math.max(height[l], lMax);
            rMax = Math.max(height[r], rMax);
            if(lMax < rMax){
                sum += lMax - height[l++];
            }else{
                sum += rMax - height[r--];
            }
        }
        return sum;       
    }
}

3.3 Trapping Rain Water JavaScript

var trap = function(height) {
    const size = height.length;
    const leftMax = new Array(size);
    const rightMax = new Array(size);
    let water = 0
    leftMax[0] = height[0]
    rightMax[size - 1] = height[size - 1];
    for (let i = 1; i < size; i++) {
        leftMax[i] = Math.max(height[i], leftMax[i - 1]);
    }
    for (let i = size - 2; i >= 0; i--) {
        rightMax[i] = Math.max(height[i], rightMax[i + 1]);
    }
    for (let i = 1; i < size - 1; i++) {
        water += Math.min(leftMax[i], rightMax[i]) - height[i]   
    }
    return water    
};

3.4 Trapping Rain Water Python

class Solution(object):
    def trap(self, height):
        i, j, ans, mx, mi = 0, len(height) - 1, 0, 0, 0
        while i <= j:
            mi = min(height[i], height[j])
            mx = max(mx, mi)
            ans += mx - mi
            if height[i] < height[j]: i += 1
            else: j -= 1
        return ans

4. Time and Space Complexity

Time ComplexitySpace Complexity
C++O(n)O(n)
JavaO(n)O(1)
JavaScriptO(n)O(n)
PythonO(n)O(1)
  • C++ and JavaScript use additional arrays for pre-computation, leading to O(n) space complexity.
  • Java and Python use the Two Pointers approach, which is more space-efficient with O(1) space complexity.
  • All implementations have a time complexity of O(n) because they involve linear traversal of the input array.
Scroll to Top