Trapping Rain Water
Description
You are given an array of n non-negative integers called height, where each element represents the height of a bar in an elevation map. Every bar has a width of 1 unit.
Your task is to compute how much rainwater can be trapped between the bars after it rains.
Water gets trapped at a position whenever there exists at least one taller bar somewhere to its left and at least one taller bar somewhere to its right. The amount of water at a particular position equals the minimum of the tallest bar on its left and the tallest bar on its right, minus the height of the bar at that position.
Return the total units of water trapped across all positions.
Examples
Example 1
Input: height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
Output: 6
Explanation: The elevation map (represented by the array) traps 6 units of rain water. Water fills the valleys:
- Index 2: min(1, 3) − 0 = 1 unit
- Index 4: min(2, 3) − 1 = 1 unit
- Index 5: min(2, 3) − 0 = 2 units
- Index 6: min(2, 3) − 1 = 1 unit
- Index 9: min(3, 2) − 1 = 1 unit
Total = 1 + 1 + 2 + 1 + 1 = 6 units.
Example 2
Input: height = [4, 2, 0, 3, 2, 5]
Output: 9
Explanation:
- Index 1: min(4, 5) − 2 = 2 units
- Index 2: min(4, 5) − 0 = 4 units
- Index 3: min(4, 5) − 3 = 1 unit
- Index 4: min(4, 5) − 2 = 2 units
Total = 2 + 4 + 1 + 2 = 9 units.
Example 3
Input: height = [1, 2, 3, 4]
Output: 0
Explanation: The bars are strictly increasing — there is no taller bar to the right of any position that could form a right wall. Water cannot be trapped when the heights are monotonically non-decreasing (or non-increasing). The answer is 0.
Constraints
- 1 ≤ n ≤ 2 × 10⁴
- 0 ≤ height[i] ≤ 10⁵
Editorial
Brute Force
Intuition
The most direct way to think about this problem is to ask: for each individual bar, how much water sits above it?
Imagine standing on top of one bar and looking left and right. The water level above you is determined by the shorter of the two tallest walls on either side. If the tallest bar to your left is 5 and the tallest bar to your right is 3, the water can only rise to level 3 — it would spill over the shorter wall otherwise. The water above your bar is then min(leftMax, rightMax) − height[i].
The brute force approach does exactly this for every bar: scan everything to the left to find the tallest bar, scan everything to the right to find the tallest bar, and compute the trapped water at that position.
Because we do a full left scan and a full right scan for each of the n bars, the total work is O(n) per bar × n bars = O(n²). This is simple to understand but very slow for large inputs.
Step-by-Step Explanation
Let's trace through with height = [3, 0, 2, 0, 4].
Step 1 — Index 0 (height 3): This is the first bar. There is nothing to the left, so leftMax = 3 (itself). rightMax = max(0, 2, 0, 4) = 4. Water = min(3, 4) − 3 = 0. No water above the first bar.
Step 2 — Index 1 (height 0): Scan left: leftMax = max(3) = 3. Scan right: rightMax = max(2, 0, 4) = 4. Water = min(3, 4) − 0 = 3 units trapped here.
Step 3 — Index 2 (height 2): Scan left: leftMax = max(3, 0) = 3. Scan right: rightMax = max(0, 4) = 4. Water = min(3, 4) − 2 = 1 unit trapped here.
Step 4 — Index 3 (height 0): Scan left: leftMax = max(3, 0, 2) = 3. Scan right: rightMax = max(4) = 4. Water = min(3, 4) − 0 = 3 units trapped here.
Step 5 — Index 4 (height 4): This is the last bar. leftMax = max(3, 0, 2, 0) = 3. rightMax = 4 (itself). Water = min(3, 4) − 4 = −1 → clamped to 0. No water above the last bar.
Total: 0 + 3 + 1 + 3 + 0 = 7 units.
Algorithm
- Initialize
totalWater = 0. - For each index
ifrom 0 to n − 1:
a. Scan left from index 0 to i and findleftMax(maximum height in that range).
b. Scan right from index i to n − 1 and findrightMax(maximum height in that range).
c. Computewater = min(leftMax, rightMax) − height[i].
d. Ifwater > 0, add it tototalWater. - Return
totalWater.
Code
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
int totalWater = 0;
for (int i = 0; i < n; i++) {
// Find the tallest bar to the left (including i)
int leftMax = 0;
for (int j = 0; j <= i; j++) {
leftMax = max(leftMax, height[j]);
}
// Find the tallest bar to the right (including i)
int rightMax = 0;
for (int j = i; j < n; j++) {
rightMax = max(rightMax, height[j]);
}
// Water above bar i
totalWater += min(leftMax, rightMax) - height[i];
}
return totalWater;
}
};class Solution:
def trap(self, height: list[int]) -> int:
n = len(height)
total_water = 0
for i in range(n):
# Tallest bar to the left (including i)
left_max = max(height[:i + 1])
# Tallest bar to the right (including i)
right_max = max(height[i:])
# Water above bar i
total_water += min(left_max, right_max) - height[i]
return total_waterclass Solution {
public int trap(int[] height) {
int n = height.length;
int totalWater = 0;
for (int i = 0; i < n; i++) {
// Find the tallest bar to the left (including i)
int leftMax = 0;
for (int j = 0; j <= i; j++) {
leftMax = Math.max(leftMax, height[j]);
}
// Find the tallest bar to the right (including i)
int rightMax = 0;
for (int j = i; j < n; j++) {
rightMax = Math.max(rightMax, height[j]);
}
// Water above bar i
totalWater += Math.min(leftMax, rightMax) - height[i];
}
return totalWater;
}
}Complexity Analysis
Time Complexity: O(n²)
For each of the n bars, we perform two linear scans (one left, one right), each up to O(n). Total work: n × O(n) = O(n²).
Space Complexity: O(1)
We only use a constant number of variables (leftMax, rightMax, totalWater). No auxiliary data structures are allocated.
Why This Approach Is Not Efficient
The brute force solution re-computes the same information over and over. When we compute leftMax at index 5, we scan indices 0 through 5. When we then compute leftMax at index 6, we scan indices 0 through 6 — repeating all the work from the previous step plus one more comparison.
This redundant scanning is the core inefficiency. The left maximum at index i is simply max(leftMax[i-1], height[i]) — it only depends on the previous answer and the current bar. Likewise, the right maximum at index i is max(rightMax[i+1], height[i]).
If we precompute these running maximums in two linear passes, we can answer every bar's query in O(1) instead of O(n), reducing the total time from O(n²) to O(n) at the cost of O(n) extra space.
Better Approach - Prefix Max Arrays
Intuition
The key observation from the brute force is that leftMax[i] only depends on leftMax[i-1] and height[i], and rightMax[i] only depends on rightMax[i+1] and height[i]. This is a classic prefix / suffix maximum pattern.
We build two arrays:
- leftMax[i] = the tallest bar from the start up to position i (inclusive). Computed with a single left-to-right pass.
- rightMax[i] = the tallest bar from position i to the end (inclusive). Computed with a single right-to-left pass.
Once both arrays are built, the water at any position i is instantly available as min(leftMax[i], rightMax[i]) − height[i]. We simply sum this across all positions.
This trades O(n) extra space for a dramatic speedup: every bar is now processed in O(1) time, giving O(n) total time.
Step-by-Step Explanation
Trace with height = [3, 0, 2, 0, 4].
Phase 1 — Build leftMax (scan left → right):
- leftMax[0] = 3 (first bar)
- leftMax[1] = max(3, 0) = 3
- leftMax[2] = max(3, 2) = 3
- leftMax[3] = max(3, 0) = 3
- leftMax[4] = max(3, 4) = 4
- Result: leftMax = [3, 3, 3, 3, 4]
Phase 2 — Build rightMax (scan right → left):
- rightMax[4] = 4 (last bar)
- rightMax[3] = max(4, 0) = 4
- rightMax[2] = max(4, 2) = 4
- rightMax[1] = max(4, 0) = 4
- rightMax[0] = max(4, 3) = 4
- Result: rightMax = [4, 4, 4, 4, 4]
Phase 3 — Compute water at each index:
- i=0: min(3,4) − 3 = 0
- i=1: min(3,4) − 0 = 3
- i=2: min(3,4) − 2 = 1
- i=3: min(3,4) − 0 = 3
- i=4: min(4,4) − 4 = 0
Total: 0 + 3 + 1 + 3 + 0 = 7 units.
Prefix Max Arrays — Build leftMax, rightMax, Compute Water — Visualizes the prefix max array construction and water computation on height = [3, 0, 2, 0, 4].
Algorithm
- Create an array
leftMaxof size n. SetleftMax[0] = height[0]. - Scan left to right: for each
ifrom 1 to n−1, setleftMax[i] = max(leftMax[i−1], height[i]). - Create an array
rightMaxof size n. SetrightMax[n−1] = height[n−1]. - Scan right to left: for each
ifrom n−2 down to 0, setrightMax[i] = max(rightMax[i+1], height[i]). - Initialize
totalWater = 0. - For each
ifrom 0 to n−1, addmin(leftMax[i], rightMax[i]) − height[i]tototalWater. - Return
totalWater.
Code
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
if (n <= 2) return 0;
// Build prefix max (left to right)
vector<int> leftMax(n);
leftMax[0] = height[0];
for (int i = 1; i < n; i++) {
leftMax[i] = max(leftMax[i - 1], height[i]);
}
// Build suffix max (right to left)
vector<int> rightMax(n);
rightMax[n - 1] = height[n - 1];
for (int i = n - 2; i >= 0; i--) {
rightMax[i] = max(rightMax[i + 1], height[i]);
}
// Compute total water
int totalWater = 0;
for (int i = 0; i < n; i++) {
totalWater += min(leftMax[i], rightMax[i]) - height[i];
}
return totalWater;
}
};class Solution:
def trap(self, height: list[int]) -> int:
n = len(height)
if n <= 2:
return 0
# Build prefix max (left to right)
left_max = [0] * n
left_max[0] = height[0]
for i in range(1, n):
left_max[i] = max(left_max[i - 1], height[i])
# Build suffix max (right to left)
right_max = [0] * n
right_max[n - 1] = height[n - 1]
for i in range(n - 2, -1, -1):
right_max[i] = max(right_max[i + 1], height[i])
# Compute total water
total_water = 0
for i in range(n):
total_water += min(left_max[i], right_max[i]) - height[i]
return total_waterclass Solution {
public int trap(int[] height) {
int n = height.length;
if (n <= 2) return 0;
// Build prefix max (left to right)
int[] leftMax = new int[n];
leftMax[0] = height[0];
for (int i = 1; i < n; i++) {
leftMax[i] = Math.max(leftMax[i - 1], height[i]);
}
// Build suffix max (right to left)
int[] rightMax = new int[n];
rightMax[n - 1] = height[n - 1];
for (int i = n - 2; i >= 0; i--) {
rightMax[i] = Math.max(rightMax[i + 1], height[i]);
}
// Compute total water
int totalWater = 0;
for (int i = 0; i < n; i++) {
totalWater += Math.min(leftMax[i], rightMax[i]) - height[i];
}
return totalWater;
}
}Complexity Analysis
Time Complexity: O(n)
We make three linear passes through the array — one to build leftMax, one to build rightMax, and one to sum the water. Each pass is O(n), so the total is O(n).
Space Complexity: O(n)
We allocate two auxiliary arrays (leftMax and rightMax) each of size n, using O(n) extra space.
Why This Approach Is Not Efficient
The prefix max approach achieves optimal O(n) time — we cannot do better on time because we must examine every bar at least once. However, it uses O(n) extra space for the two auxiliary arrays.
Notice an interesting property: when computing water at index i, we only need leftMax[i] and rightMax[i]. If we process bars from left and right simultaneously using two pointers, we can maintain just two variables (leftMax and rightMax) instead of two full arrays.
The key insight is: if leftMax < rightMax, we know the water at the left pointer is determined by leftMax alone — the right side is guaranteed to be at least as tall. Similarly, if rightMax ≤ leftMax, the water at the right pointer is determined by rightMax. This lets us process one bar per step while only tracking two running maximums, reducing space to O(1).
Optimal Approach - Two Pointers
Intuition
Instead of precomputing full arrays, we use two pointers — one starting from the left and one from the right — that walk toward each other.
We maintain two variables:
leftMax: the tallest bar seen so far from the left pointer's side.rightMax: the tallest bar seen so far from the right pointer's side.
At each step, we compare leftMax and rightMax:
- If
leftMax < rightMax: the water at the left pointer's position is constrained byleftMax(because we know there's something at least as tall asrightMaxon the right, so the bottleneck is the left). We compute water asleftMax − height[left], then advance the left pointer. - If
rightMax ≤ leftMax: symmetrically, the water at the right pointer's position is constrained byrightMax. We compute water asrightMax − height[right], then advance the right pointer.
This works because the pointer on the side with the smaller maximum is the one whose water level we can determine with certainty — the other side is guaranteed to have an equal or taller wall somewhere.
The two pointers meet in the middle after exactly n steps, giving us O(n) time and O(1) space.
Step-by-Step Explanation
Trace with height = [3, 0, 2, 0, 4].
Initialize: left = 0, right = 4, leftMax = 0, rightMax = 0, totalWater = 0.
Step 1: height[left=0] = 3, height[right=4] = 4. Update leftMax = max(0, 3) = 3, rightMax = max(0, 4) = 4. Since leftMax(3) < rightMax(4), process left: water += 3 − 3 = 0. Move left → 1.
Step 2: height[left=1] = 0, height[right=4] = 4. Update leftMax = max(3, 0) = 3. Since leftMax(3) < rightMax(4), process left: water += 3 − 0 = 3. totalWater = 3. Move left → 2.
Step 3: height[left=2] = 2, height[right=4] = 4. Update leftMax = max(3, 2) = 3. Since leftMax(3) < rightMax(4), process left: water += 3 − 2 = 1. totalWater = 4. Move left → 3.
Step 4: height[left=3] = 0, height[right=4] = 4. Update leftMax = max(3, 0) = 3. Since leftMax(3) < rightMax(4), process left: water += 3 − 0 = 3. totalWater = 7. Move left → 4.
Step 5: left(4) ≥ right(4), loop ends.
Result: totalWater = 7.
Two Pointers — Converging from Both Ends — Two-pointer technique on height = [4, 2, 0, 3, 2, 5] showing how left and right pointers converge while tracking running maximums and accumulating trapped water.
Algorithm
- Initialize
left = 0,right = n − 1,leftMax = 0,rightMax = 0,totalWater = 0. - While
left < right:
a. UpdateleftMax = max(leftMax, height[left]).
b. UpdaterightMax = max(rightMax, height[right]).
c. IfleftMax < rightMax:- Add
leftMax − height[left]tototalWater. - Increment
left.
d. Else: - Add
rightMax − height[right]tototalWater. - Decrement
right.
- Add
- Return
totalWater.
Code
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
if (n <= 2) return 0;
int left = 0, right = n - 1;
int leftMax = 0, rightMax = 0;
int totalWater = 0;
while (left < right) {
leftMax = max(leftMax, height[left]);
rightMax = max(rightMax, height[right]);
if (leftMax < rightMax) {
totalWater += leftMax - height[left];
left++;
} else {
totalWater += rightMax - height[right];
right--;
}
}
return totalWater;
}
};class Solution:
def trap(self, height: list[int]) -> int:
n = len(height)
if n <= 2:
return 0
left, right = 0, n - 1
left_max, right_max = 0, 0
total_water = 0
while left < right:
left_max = max(left_max, height[left])
right_max = max(right_max, height[right])
if left_max < right_max:
total_water += left_max - height[left]
left += 1
else:
total_water += right_max - height[right]
right -= 1
return total_waterclass Solution {
public int trap(int[] height) {
int n = height.length;
if (n <= 2) return 0;
int left = 0, right = n - 1;
int leftMax = 0, rightMax = 0;
int totalWater = 0;
while (left < right) {
leftMax = Math.max(leftMax, height[left]);
rightMax = Math.max(rightMax, height[right]);
if (leftMax < rightMax) {
totalWater += leftMax - height[left];
left++;
} else {
totalWater += rightMax - height[right];
right--;
}
}
return totalWater;
}
}Complexity Analysis
Time Complexity: O(n)
Each iteration of the while loop advances either the left pointer forward or the right pointer backward. Together they cover all n positions exactly once, so the loop runs at most n times. Each iteration does O(1) work (comparisons, additions). Total: O(n).
Space Complexity: O(1)
We use only a fixed number of variables (left, right, leftMax, rightMax, totalWater) regardless of input size. No arrays or data structures are allocated. This is the optimal space usage.