Log inSign up
hardLeetCodeNot Started

Trapping Rain Water

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

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.

Each bar's height is given in the array height. Water is trapped between elevation bars whenever there are taller bars on both its left and right sides.

Example 1 · Standard Elevation Map:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The elevation map [0,1,0,2,1,0,1,3,2,1,2,1] traps 6 units of rain water (at indices 2, 4, 5, 6, 9, 10).

Example 2 · V-Shape Valley:

Input: height = [4,2,0,3,2,5]
Output: 9
Explanation: Water trapped: index 1 traps 2, index 2 traps 4, index 3 traps 1, index 4 traps 2. Total = 2 + 4 + 1 + 2 = 9.

Constraints:

  • n == height.length
  • 1 <= n <= 2 * 104
  • 0 <= height[i] <= 105

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Two Pointers technique
  • Prefix/Suffix maximum concepts
  • Basic array traversals and bounds checking

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand the mathematical formulation of trapped water per bar.
  • Learn how to optimize O(N2) repeated scans to O(N) with prefix/suffix arrays.
  • Master the two-pointer invariant: when leftMax < rightMax, the left side is bottlenecked purely by leftMax.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Problem asks to calculate trapped volume/area between bars/elevations.
  • Each position's capacity depends on the surrounding boundary maximums.
  • Look for converging two pointers where decisions depend on comparing current maximum boundaries.

Algorithmic Decision Tree:

  • If we need O(1) extra space, maintain leftMax and rightMax pointers and move the pointer with the smaller boundary inward.
  • If visualizing level-by-level, a Monotonic Decreasing Stack can calculate horizontal trapped water slices.

Connected Patterns:

Container With Most WaterLargest Rectangle in HistogramProduct of Array Except Self

1. Brute Force — Recompute Left & Right Max per Element

Intuition

At each bar, search all elements to the left to find the tallest left wall, and search all elements to the right to find the tallest right wall. The trapped water is min(maxLeft, maxRight) - height[i].

Algorithm

  1. At each bar, search all elements to the left to find the tallest left wall, and search all elements to the right to find the tallest right wall
  2. The trapped water is min(maxLeft, maxRight) - height[i].

Brute Force Column-by-Column Water Trapping Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [3, 0, 2, 0, 4]
Current operationSTEP 1 OF 6
Column 0 (Boundary): Water spills out to the left
Visual state
Values and pointers at this exact step
table
S
3
0
2
0
4
0
↑ i=0 (Boundary)
1
2
3
4
Col0
Height3
Left Max3
Right Max4
Water0
Total Water0
Variables at this step
Col
0
Height
3
Left Max
3
Right Max
4
Water
0
Total Water
0
Check / comparison
Left boundary column has no left walls. Trapped water = 0.
Decision / next transition
Water at index 0 = 0. Advance to index 1.
Why this step matters

Column 0 (Boundary): Water spills out to the left. Boundary columns cannot trap water.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 int trap(vector<int>& height) {
10 int n = height.size();
11 int totalWater = 0;
12
13 for (int i = 0; i < n; i++) {
14 int maxLeft = 0;
15 for (int j = 0; j <= i; j++) {
16 maxLeft = max(maxLeft, height[j]);
17 }
18
19 int maxRight = 0;
20 for (int j = i; j < n; j++) {
21 maxRight = max(maxRight, height[j]);
22 }
23
24 totalWater += min(maxLeft, maxRight) - height[i];
25 }
26
27 return totalWater;
28 }
29};
30
31int main() {
32 Solution sol;
33 vector<int> height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
34 cout << "Input: [0,1,0,2,1,0,1,3,2,1,2,1]\n";
35 cout << "Brute Force Trapped Water: " << sol.trap(height) << "\n";
36 return 0;
37}

Time & Space Complexity

  • Time complexity: O(N^2) — Time complexity for Brute Force — Recompute Left & Right Max per Element.
  • Space complexity: O(1) — Space complexity for Brute Force — Recompute Left & Right Max per Element.

Why Brute Force Doesn't Scale:

With N = 20,000, O(N2) requires 4 * 108 operations, exceeding standard 1-second execution limits.

Two pointers reduces 400,000,000 operations to just 20,000 operations (20,000x speedup), using zero extra memory.

2. Better — Precomputed Prefix and Suffix Max Arrays

Intuition

Instead of recalculating maxLeft and maxRight at each index, precompute leftMax[i] (prefix maximums from 0 to i) and rightMax[i] (suffix maximums from i to n-1) in O(N) passes.

Algorithm

  1. Initialize required state variables and allocate data structures for Better — Precomputed Prefix and Suffix Max Arrays.
  2. Iterate through the input array and apply the core algorithmic condition.
  3. Update boundaries, frequencies, or pointers in accordance with the invariant.
  4. Return the computed result or transformed array.

Precomputed Prefix & Suffix Max Water Trapping

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [3, 0, 2, 0, 4]
Current operationSTEP 1 OF 6
Pass 1 — Precompute Left Max: For every index i, store max(leftMax[i-1], height[i])
Visual state
Values and pointers at this exact step
table
S
3
3
3
3
4
0
↑ leftMax Array
1
2
3
4
leftMax[3, 3, 3, 3, 4]
TimeO(N)
Variables at this step
leftMax
[3, 3, 3, 3, 4]
Time
O(N)
Check / comparison
leftMax = [3, 3, 3, 3, 4] precomputed in a forward pass.
Decision / next transition
Stores the highest left wall encountered so far for each column.
Why this step matters

Pass 1 — Precompute Left Max: For every index i, store max(leftMax[i-1], height[i]).

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 int trap(vector<int>& height) {
10 int n = height.size();
11 if (n == 0) return 0;
12
13 vector<int> leftMax(n), rightMax(n);
14 leftMax[0] = height[0];
15 for (int i = 1; i < n; i++) {
16 leftMax[i] = max(leftMax[i - 1], height[i]);
17 }
18
19 rightMax[n - 1] = height[n - 1];
20 for (int i = n - 2; i >= 0; i--) {
21 rightMax[i] = max(rightMax[i + 1], height[i]);
22 }
23
24 int totalWater = 0;
25 for (int i = 0; i < n; i++) {
26 totalWater += min(leftMax[i], rightMax[i]) - height[i];
27 }
28
29 return totalWater;
30 }
31};
32
33int main() {
34 Solution sol;
35 vector<int> height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
36 cout << "Input: [0,1,0,2,1,0,1,3,2,1,2,1]\n";
37 cout << "Better (Prefix/Suffix) Trapped Water: " << sol.trap(height) << "\n";
38 return 0;
39}

Time & Space Complexity

  • Time complexity: O(N log N) — Time complexity for Better — Precomputed Prefix and Suffix Max Arrays.
  • Space complexity: O(N) — Space complexity for Better — Precomputed Prefix and Suffix Max Arrays.

3. Optimal — Converging Two Pointers

Intuition

Maintain left and right pointers. If leftMax <= rightMax, then water at left is bounded strictly by leftMax (since a wall at least as high as rightMax >= leftMax exists on the right). We process left and advance it. Otherwise, process right and decrement it.

Algorithm

  1. Maintain left and right pointers
  2. If leftMax <= rightMax, then water at left is bounded strictly by leftMax (since a wall at least as high as rightMax >= leftMax exists on the right)
  3. We process left and advance it
  4. Otherwise, process right and decrement it.

Two-Pointer Elevation Trapping Water Trace

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
InputINPUT nums = [3, 0, 2, 0, 4]
Current operationSTEP 1 OF 5
Step 1 — Setup & Left Bottleneck: Pointers start at ends (L=0, R=4)
Visual state
Values and pointers at this exact step
pointers
S
3
0
2
0
4
0
↑ L
1
2
3
4
↑ R
Variables at this step
L Pointer
Idx 0 (h=3)
R Pointer
Idx 4 (h=4)
leftMax
3
rightMax
4
Water Trapped
0
Check / comparison
leftMax = 3, rightMax = 4. Since leftMax (3) < rightMax (4), left side bottleneck dictates water.
Decision / next transition
Advance L to index 1. Water trapped at L depends strictly on leftMax.
Why this step matters

Step 1 — Setup & Left Bottleneck: Pointers start at ends (L=0, R=4). leftMax = 3, rightMax = 4. Because leftMax < rightMax, we know with 100% certainty that the right boundary is tall enough to support water up to leftMax. We advance L to index 1.

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 int trap(vector<int>& height) {
10 int left = 0, right = height.size() - 1;
11 int leftMax = 0, rightMax = 0;
12 int totalWater = 0;
13
14 while (left < right) {
15 if (height[left] <= height[right]) {
16 if (height[left] >= leftMax) {
17 leftMax = height[left];
18 } else {
19 totalWater += leftMax - height[left];
20 }
21 left++;
22 } else {
23 if (height[right] >= rightMax) {
24 rightMax = height[right];
25 } else {
26 totalWater += rightMax - height[right];
27 }
28 right--;
29 }
30 }
31
32 return totalWater;
33 }
34};
35
36int main() {
37 Solution sol;
38 vector<int> height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
39 cout << "Input: [0,1,0,2,1,0,1,3,2,1,2,1]\n";
40 cout << "Optimal (Two Pointers) Trapped Water: " << sol.trap(height) << "\n";
41 return 0;
42}

Time & Space Complexity

  • Time complexity: O(N) — Time complexity for Optimal — Converging Two Pointers.
  • Space complexity: O(1) — Space complexity for Optimal — Converging Two Pointers.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Recompute Left & Right Max per ElementO(N^2)O(1)For each element i, scan left to find maxLeft and right to find maxRight. Add min(maxLeft, maxRight) - height[i] to total.Redundant maximum searches for every index.
2.Better — Precomputed Prefix and Suffix Max ArraysO(N)O(N)Precompute leftMax[i] in a forward pass and rightMax[i] in a backward pass. Then compute water in a third pass.Auxiliary space allocations for prefix and suffix arrays.
3.Optimal — Converging Two PointersOptimalO(N)O(1)Maintain two pointers (left, right) and their running maximums (leftMax, rightMax). Move the pointer with the smaller max inward.None; theoretical lower bound achieved.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • Edge Case — Input: `, Expected: ` —
  • Edge Case — Input: `, Expected: ` —
  • Edge Case — Input: `, Expected: ` —

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Trapping Rain Water?

2.Why is the brute force approach suboptimal for large inputs in Trapping Rain Water?

3.Which data structure or technique enables the optimal solution for Trapping Rain Water?

Back to DSA Sheet