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
Table of Contents
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.

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 Complexity | Space Complexity | |
C++ | O(n) | O(n) |
Java | O(n) | O(1) |
JavaScript | O(n) | O(n) |
Python | O(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.