Trapping Rain Water solution and explanation
9 more videos on this problem
Trapping Rain Water - Google Interview Question - Leetcode 42NeetCode · 23:21 · 770K views
L8. Trapping Rainwater | 2 Approaches | Stack and Queue Playlisttake U forward · 28:58 · 407K views
Trapping Rainwater Problem | Leetcode #42Techdose · 34:12 · 106K views
Trapping Rain Water | without stack | Made Super Easy | Leetcode 42 | codestorywithMIKcodestorywithMIK · 20:00 · 67K views
Trapping Rain Water - Leetcode 42 - 2 Pointers (Python)Greg Hogg · 9:51 · 48K views
How to Solve Trapping Rainwater in 2 MINUTES - Leetcode HARD Interview QuestionBen Dickey · 2:18 · 14K views
Trapping Rainwater Problem – Brute Force and Optimized Two-Pointer Approach ExplainedRisingBrain · 22:21 · 13K views
Trapping Rain Water (LeetCode 42) | Interview Essential | Full visual solutionNikhil Lohia · 21:01 · 13K views
Goldman Sachs Coding Interview Question - Trapping Rain Water - LeetCode 42AlgoJS · 7:38 · 8K views
TRAPPING RAIN WATER | LEETCODE 42 | PYTHON SOLUTIONCracking FAANG · 21:04 · 5K views
The 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.
Example 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
Constraints:
n == height.length1 <= n <= 2 * 1040 <= height[i] <= 105
Approach overview
Problem Overview: You are given an array where each element represents the height of a vertical bar in an elevation map. After rain, water collects in the gaps between bars. The task is to compute how many total units of water remain trapped after the rain.
Approach 1: Two-Pass Dynamic Programming (O(n) time, O(n) space)
This approach precomputes the tallest bar on the left and right of every index. Create two arrays: leftMax[i] stores the maximum height from the start up to i, and rightMax[i] stores the maximum height from the end down to i. The water trapped above index i is min(leftMax[i], rightMax[i]) - height[i]. Iterate through the array once to fill leftMax, once for rightMax, and once more to accumulate trapped water. Time complexity is O(n) and space complexity is O(n). This method is straightforward and a good way to understand the core insight that water level depends on the shorter boundary.
This problem is a classic example involving arrays and boundary precomputation using dynamic programming style prefix/suffix information.
Approach 2: Two-Pointer Technique (O(n) time, O(1) space)
The optimal solution eliminates the extra arrays by processing from both ends simultaneously. Maintain two pointers: left at the start and right at the end. Track the highest bars seen so far from both directions using leftMax and rightMax. If height[left] < height[right], the trapped water depends only on the left side because the right boundary is guaranteed to be taller. Update leftMax or accumulate water, then move left. Otherwise process the right side similarly. Each index is visited once, producing O(n) time and O(1) extra space. This technique relies on the observation that the smaller boundary determines the water level.
This strategy is a standard pattern when solving problems with two pointers moving toward each other while maintaining partial state.
Approach 3: Monotonic Stack (O(n) time, O(n) space)
A stack-based solution processes bars while maintaining a decreasing stack of indices. When the current bar becomes taller than the bar at the top of the stack, a container boundary is discovered. Pop the stack to form a valley, compute the bounded height using the difference between the current bar and the new stack top, and multiply by the horizontal distance. Each index enters and leaves the stack once, so the time complexity remains O(n) with O(n) auxiliary space. This approach highlights how trapped water forms between two boundaries and is often discussed when learning monotonic stacks.
Recommended for interviews: Interviewers typically expect the two-pointer solution. The dynamic programming version clearly demonstrates the core insight and is a good stepping stone, but the two-pointer technique proves you can reduce memory while maintaining linear time.
Approach 1: Two-Pass Dynamic Programming
This approach involves creating two auxiliary arrays to store the maximum heights on the left and right of each bar. With these arrays, you can calculate how much water each bar can trap.
The water trapped above a bar is determined by the minimum of the maximum heights on its left and right, minus the bar's height itself.
def trap(height):
if not height: return 0
n = len(height)
left_max = [0] * n
right_max = [0] * n
water = 0
left_max[0] = height[0]
for i in range(1, n):
left_max[i] = max(height[i], left_max[i - 1])
right_max[n - 1] = height[n - 1]
for i in range(n - 2, -1, -1):
right_max[i] = max(height[i], right_max[i + 1])
for i in range(n):
water += min(left_max[i], right_max[i]) - height[i]
return water
height = [0,1,0,2,1,0,1,3,2,1,2,1]
print(f"Water trapped: {trap(height)}")public class TrappingRainWater {
public static int trap(int[] height) {
if (height == null || height.length == 0) return 0;
int n = height.length;
int[] leftMax = new int[n];
int[] rightMax = new int[n];
int water = 0;
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]);
}
for (int i = 0; i < n; i++) {
water += Math.min(leftMax[i], rightMax[i]) - height[i];
}
return water;
}
public static void main(String[] args) {
int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
System.out.println("Water trapped: " + trap(height));
}
}#include <iostream>
#include <vector>
#include <algorithm>
int trap(std::vector<int>& height) {
int n = height.size();
if (n == 0) return 0;
std::vector<int> leftMax(n), rightMax(n);
int water = 0;
leftMax[0] = height[0];
for (int i = 1; i < n; ++i) {
leftMax[i] = std::max(height[i], leftMax[i - 1]);
}
rightMax[n - 1] = height[n - 1];
for (int i = n - 2; i >= 0; --i) {
rightMax[i] = std::max(height[i], rightMax[i + 1]);
}
for (int i = 0; i < n; ++i) {
water += std::min(leftMax[i], rightMax[i]) - height[i];
}
return water;
}
int main() {
std::vector<int> height = {0,1,0,2,1,0,1,3,2,1,2,1};
std::cout << "Water trapped: " << trap(height) << std::endl;
return 0;
}function trap(height) {
if (!height.length) return 0;
const n = height.length;
const leftMax = new Array(n);
const rightMax = new Array(n);
let water = 0;
leftMax[0] = height[0];
for (let i = 1; i < n; i++) {
leftMax[i] = Math.max(height[i], leftMax[i - 1]);
}
rightMax[n - 1] = height[n - 1];
for (let i = n - 2; i >= 0; i--) {
rightMax[i] = Math.max(height[i], rightMax[i + 1]);
}
for (let i = 0; i < n; i++) {
water += Math.min(leftMax[i], rightMax[i]) - height[i];
}
return water;
}
const height = [0,1,0,2,1,0,1,3,2,1,2,1];
console.log(`Water trapped: ${trap(height)}`);#include <stdio.h>
#include <stdlib.h>
int trap(int* height, int heightSize) {
if (heightSize == 0) return 0;
int *leftMax = (int*)malloc(heightSize * sizeof(int));
int *rightMax = (int*)malloc(heightSize * sizeof(int));
int water = 0;
leftMax[0] = height[0];
for (int i = 1; i < heightSize; i++) {
leftMax[i] = height[i] > leftMax[i - 1] ? height[i] : leftMax[i - 1];
}
rightMax[heightSize - 1] = height[heightSize - 1];
for (int i = heightSize - 2; i >= 0; i--) {
rightMax[i] = height[i] > rightMax[i + 1] ? height[i] : rightMax[i + 1];
}
for (int i = 0; i < heightSize; i++) {
water += (leftMax[i] < rightMax[i] ? leftMax[i] : rightMax[i]) - height[i];
}
free(leftMax);
free(rightMax);
return water;
}
int main() {
int height[] = {0,1,0,2,1,0,1,3,2,1,2,1};
int heightSize = sizeof(height) / sizeof(height[0]);
printf("Water trapped: %d", trap(height, heightSize));
return 0;
}public class Solution {
public int Trap(int[] height) {
if (height == null || height.Length == 0) return 0;
int n = height.Length;
int[] leftMax = new int[n];
int[] rightMax = new int[n];
int water = 0;
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]);
}
for (int i = 0; i < n; i++) {
water += Math.Min(leftMax[i], rightMax[i]) - height[i];
}
return water;
}
public static void Main(string[] args) {
int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
Solution solution = new Solution();
Console.WriteLine("Water trapped: " + solution.Trap(height));
}
}This Python implementation uses two lists, left_max and right_max, to store left and right maximum heights. It uses these to compute the trapped water as it iterates through the height array.
Time Complexity: O(n) as it traverses each pass in linear time.
Space Complexity: O(n) because it maintains two separate lists the same size as the input.
Approach 2: Two-Pointer Technique
The two-pointer technique optimizes space by keeping track of the left and right bars with two pointers. It uses a single loop and calculates water based on the shorter of the two heights at the current pointers.
def trap(height):
left, right = 0, len(height) - 1
left_max = right_max = 0
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
height = [0,1,0,2,1,0,1,3,2,1,2,1]
print(f"Water trapped: {trap(height)}")public class TrappingRainWater {
public static int trap(int[] height) {
int left = 0, right = height.length - 1;
int leftMax = 0, rightMax = 0, water = 0;
while (left < right) {
if (height[left] < height[right]) {
if (height[left] >= leftMax) {
leftMax = height[left];
} else {
water += leftMax - height[left];
}
left++;
} else {
if (height[right] >= rightMax) {
rightMax = height[right];
} else {
water += rightMax - height[right];
}
right--;
}
}
return water;
}
public static void main(String[] args) {
int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
System.out.println("Water trapped: " + trap(height));
}
}#include <iostream>
#include <vector>
int trap(std::vector<int>& height) {
int left = 0, right = height.size() - 1;
int leftMax = 0, rightMax = 0, water = 0;
while (left < right) {
if (height[left] < height[right]) {
if (height[left] >= leftMax) {
leftMax = height[left];
} else {
water += leftMax - height[left];
}
++left;
} else {
if (height[right] >= rightMax) {
rightMax = height[right];
} else {
water += rightMax - height[right];
}
--right;
}
}
return water;
}
int main() {
std::vector<int> height = {0,1,0,2,1,0,1,3,2,1,2,1};
std::cout << "Water trapped: " << trap(height) << std::endl;
return 0;
}function trap(height) {
let left = 0, right = height.length - 1;
let leftMax = 0, rightMax = 0;
let water = 0;
while (left < right) {
if (height[left] < height[right]) {
if (height[left] >= leftMax) {
leftMax = height[left];
} else {
water += leftMax - height[left];
}
left++;
} else {
if (height[right] >= rightMax) {
rightMax = height[right];
} else {
water += rightMax - height[right];
}
right--;
}
}
return water;
}
const height = [0,1,0,2,1,0,1,3,2,1,2,1];
console.log(`Water trapped: ${trap(height)}`);#include <stdio.h>
int trap(int* height, int heightSize) {
if (heightSize == 0) return 0;
int left = 0, right = heightSize - 1;
int leftMax = 0, rightMax = 0, water = 0;
while (left < right) {
if (height[left] < height[right]) {
if (height[left] >= leftMax) {
leftMax = height[left];
} else {
water += leftMax - height[left];
}
left++;
} else {
if (height[right] >= rightMax) {
rightMax = height[right];
} else {
water += rightMax - height[right];
}
right--;
}
}
return water;
}
int main() {
int height[] = {0,1,0,2,1,0,1,3,2,1,2,1};
int heightSize = sizeof(height) / sizeof(height[0]);
printf("Water trapped: %d", trap(height, heightSize));
return 0;
}public class Solution {
public int Trap(int[] height) {
int left = 0, right = height.Length - 1;
int leftMax = 0, rightMax = 0, water = 0;
while (left < right) {
if (height[left] < height[right]) {
if (height[left] >= leftMax) {
leftMax = height[left];
} else {
water += leftMax - height[left];
}
left++;
} else {
if (height[right] >= rightMax) {
rightMax = height[right];
} else {
water += rightMax - height[right];
}
right--;
}
}
return water;
}
public static void Main(string[] args) {
int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
Solution solution = new Solution();
Console.WriteLine("Water trapped: " + solution.Trap(height));
}
}Implementing a two-pointer approach, this Python code starts pointers at each end of the list. Comparing left and right values, it iterates inward to update max heights and compute trapped rainwater efficiently.
Time Complexity: O(n), due to a one-time traversal across the list.
Space Complexity: O(1), as there's no use of additional storage structures beyond a few integral variables.
Approach 3: Dynamic Programming
We define left[i] as the height of the highest bar to the left of and including the position at index i, and right[i] as the height of the highest bar to the right of and including the position at index i. Therefore, the amount of rainwater that can be trapped at index i is min(left[i], right[i]) - height[i]. We traverse the array to calculate left[i] and right[i], and the final answer is sum_{i=0}^{n-1} min(left[i], right[i]) - height[i].
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array.
function trap(height: number[]): number {
const n = height.length;
const left: number[] = new Array(n).fill(height[0]);
const right: number[] = new Array(n).fill(height[n - 1]);
for (let i = 1; i < n; ++i) {
left[i] = Math.max(left[i - 1], height[i]);
right[n - i - 1] = Math.max(right[n - i], height[n - i - 1]);
}
let ans = 0;
for (let i = 0; i < n; ++i) {
ans += Math.min(left[i], right[i]) - height[i];
}
return ans;
}func trap(height []int) (ans int) {
n := len(height)
left := make([]int, n)
right := make([]int, n)
left[0], right[n-1] = height[0], height[n-1]
for i := 1; i < n; i++ {
left[i] = max(left[i-1], height[i])
right[n-i-1] = max(right[n-i], height[n-i-1])
}
for i, h := range height {
ans += min(left[i], right[i]) - h
}
return
}impl Solution {
#[allow(dead_code)]
pub fn trap(height: Vec<i32>) -> i32 {
let n = height.len();
let mut left: Vec<i32> = vec![0; n];
let mut right: Vec<i32> = vec![0; n];
left[0] = height[0];
right[n - 1] = height[n - 1];
// Initialize the left & right vector
for i in 1..n {
left[i] = std::cmp::max(left[i - 1], height[i]);
right[n - i - 1] = std::cmp::max(right[n - i], height[n - i - 1]);
}
let mut ans = 0;
// Calculate the ans
for i in 0..n {
ans += std::cmp::min(left[i], right[i]) - height[i];
}
ans
}
}class Solution {
/**
* @param integer[] $height
* @return integer
*/
function trap($height) {
$n = count($height);
if ($n == 0) {
return 0;
}
$left = 0;
$right = $n - 1;
$leftMax = 0;
$rightMax = 0;
$ans = 0;
while ($left < $right) {
if ($height[$left] < $height[$right]) {
if ($height[$left] > $leftMax) {
$leftMax = $height[$left];
} else {
$ans += $leftMax - $height[$left];
}
$left++;
} else {
if ($height[$right] > $rightMax) {
$rightMax = $height[$right];
} else {
$ans += $rightMax - $height[$right];
}
$right--;
}
}
return $ans;
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Two-Pass Dynamic Programming | Time Complexity: O(n) as it traverses each pass in linear time. |
| Two-Pointer Technique | Time Complexity: O(n), due to a one-time traversal across the list. |
| Dynamic Programming | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pass Dynamic Programming | O(n) | O(n) | When clarity matters and extra memory is acceptable |
| Two-Pointer Technique | O(n) | O(1) | Optimal interview solution with constant extra space |
| Monotonic Stack | O(n) | O(n) | Useful when learning stack-based boundary detection |
Frequently asked questions
Is Trapping Rain Water easy or hard?
Most platforms classify Trapping Rain Water as a Hard problem because the optimal insight is not immediately obvious. Many developers first implement the dynamic programming approach before discovering the more space-efficient two-pointer solution.
How to solve Trapping Rain Water in O(n)?
Use either prefix/suffix maximum arrays or the two-pointer technique. The key observation is that the water level at index i depends on the minimum of the tallest bar to its left and right. By maintaining these boundaries efficiently, you can compute trapped water in a single linear pass.
Trapping Rain Water Python or Java solution
In Python or Java, the typical implementation uses two pointers moving toward each other while maintaining leftMax and rightMax values. Each step calculates trapped water based on the smaller boundary. The algorithm runs in O(n) time and O(1) space.
What is the best approach for Trapping Rain Water?
The two-pointer technique is widely considered the best approach. It processes the array from both ends while tracking the highest bars seen so far. This achieves O(n) time and O(1) extra space, which is optimal compared with dynamic programming approaches that require additional arrays.
What data structure is used in Trapping Rain Water?
Common solutions rely on arrays and pointer manipulation. Some implementations also use a monotonic stack to track decreasing heights and detect water containers. However, the most optimal approach typically uses two pointers with constant extra space.
What is the time complexity of Trapping Rain Water?
Optimal solutions run in O(n) time because the height array is processed only once. Both the two-pointer method and the dynamic programming approach achieve linear time. The difference lies in space usage, where dynamic programming uses O(n) memory while the two-pointer approach uses O(1).
Is Trapping Rain Water asked at Google or Amazon interviews?
Trapping Rain Water is a well-known interview problem frequently reported at companies like Google, Amazon, Meta, and Microsoft. It tests understanding of arrays, boundary conditions, and space optimization techniques such as two pointers or monotonic stacks.