Trapping Rain Water — Problem Statement & Solution Guide
Problem Description
You are given an array of non‑negative integers where each element represents the height of a building standing on a flat terrain. When it rains, water can accumulate between taller buildings. Your task is to compute the total volume of water that can be trapped after the rain has stopped. The answer should be a single integer representing the number of unit squares of water that can be held.
Input: An array of integers nums of length n (1 ≤ n ≤ 10^5). Each nums[i] satisfies 0 ≤ nums[i] ≤ 10^9.
Output: A single integer – the total amount of trapped water.
The solution must run in linear time and use constant extra space beyond the input array.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Trapping Rain Water"
WHY DOES IT MATTER?
The two‑pointer pattern transforms a seemingly quadratic problem into linear time by exploiting monotonic relationships, a skill that recurs in sliding‑window, partition, and merge‑sort variants. Mastery of this pattern signals a candidate's ability to reason about data flow and eliminate unnecessary work.
OPTIMIZATION CHALLENGE
The key insight is that the trapped water at any position is limited by the smaller of the maximum heights on its left and right. By always advancing the pointer with the lower current max, we guarantee that the limiting side is already known, allowing constant‑time computation per element.
REAL-WORLD CONNECTION
Think of a dam system where water flows from higher reservoirs to lower ones; the left and right pointers act as sensors measuring the highest upstream and downstream water levels, dictating how much water can be stored at each segment of the riverbed.
During an interview, write the two‑pointer loop first, then immediately add the left_max/right_max updates and water accumulation inside the same conditional block—this keeps the code tight and avoids off‑by‑one errors.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The Trapping Rain Water problem is a classic illustration of how local maxima and minima interact in a one‑dimensional elevation map. A naive scan that computes water at each index by looking left and right for the tallest bar leads to O(n²) time, which quickly becomes infeasible for large inputs (n up to 10⁶) because each element would be examined repeatedly. The optimal paradigm leverages the two‑pointer technique combined with the concept of "left max" and "right max"—the highest bar seen so far from each direction. By maintaining these running maxima, we can decide at each step which side limits the water level, allowing us to compute the trapped volume in a single linear pass. This approach eliminates redundant scans, reduces the time complexity to O(n), and uses only O(1) extra space, satisfying the constraints of high‑performance interview problems.
Interview Questions on This Problem
Q1How would you modify the two‑pointer solution to also return the indices of the bars that actually trap water?
While moving the pointers, whenever you add water for index i, push i into a result list; the left pointer contributes when left_max <= right_max, and the right pointer contributes when right_max < left_max. The final list contains all indices that contributed positive water volume.
Q2Explain why the two‑pointer method works even when the elevation map contains large flat regions (consecutive bars of equal height).
Flat regions do not affect the invariant that the side with the smaller max height bounds the water level. As the pointers move inward, equal heights simply update left_max or right_max without changing the decision rule, ensuring correct water calculation across flat stretches.
Q3A fintech platform needs to process millions of elevation arrays in real time. Which implementation details would you prioritize to meet latency SLAs?
Prioritize an in‑place O(1) space algorithm, avoid recursion, use simple integer arithmetic to prevent overflow, and pre‑allocate the result container if indices are needed. Also, leverage SIMD or parallel chunking only after confirming that the linear scan is the bottleneck.
Examples
Input
[0,1,0,2,1,0,1,3,2,1,2,1]
Output
6
Explanation: Using the two‑pointer technique, we find that water is trapped at indices 2, 4, 5, 7, 9, and 10. The amounts are 1, 1, 2, 1, 1, and 0 respectively, summing to 6.
Input
[4,2,0,3,2,5]
Output
9
Explanation: For each position, the trapped water equals the minimum of the maximum heights to its left and right minus its own height. The contributions are 2, 4, 1, and 2, totaling 9.
Input
[1,0,2,1,0,1,3]
Output
5
Explanation: Computing left and right maximums gives trapped water of 1 at index 1, 1 at index 3, 2 at index 4, and 1 at index 5. The sum is 5.
Input
[5,4,3,2,1]
Output
0
Explanation: The heights are strictly decreasing, so no valley exists to hold water; every position has no higher building on its right.
Input
[0,2,0,3,0,1,0,4]
Output
10
Explanation: Water is trapped at indices 2, 4, 5, and 6 with amounts 2, 3, 2, and 3 respectively, giving a total of 10.
Constraints
- 1 <= nums.length <= 10^5
- 0 <= nums[i] <= 10^9
- The algorithm must run in O(n) time
- The algorithm must use O(1) additional space
Optimal Approach & Strategy
Use two pointers with running leftMax and rightMax; move the pointer with the smaller max inward, add water based on the difference, and update the corresponding max in O(n) time and O(1) space.
Brute Force Approach
For each index, scan leftwards to find the maximum height, scan rightwards to find the maximum height, then compute water as min(leftMax, rightMax) - height[i].
Verified Code Solutions
function trap(height) {
let left = 0, right = height.length - 1;
let leftMax = 0, rightMax = 0;
let 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;
}
module.exports = trap;#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int trap(vector<int>& height) {
int left = 0, right = (int)height.size() - 1;
int leftMax = 0, rightMax = 0;
int 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;
}
};public class Solution {
public int trap(int[] height) {
int left = 0, right = height.length - 1;
int leftMax = 0, rightMax = 0;
int 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;
}
}from typing import List
class Solution:
def trap(self, height: List[int]) -> int:
left, right = 0, len(height) - 1
left_max = right_max = 0
ans = 0
while left < right:
if height[left] < height[right]:
if height[left] >= left_max:
left_max = height[left]
else:
ans += left_max - height[left]
left += 1
else:
if height[right] >= right_max:
right_max = height[right]
else:
ans += right_max - height[right]
right -= 1
return ansfunction trap(height) {
let left = 0, right = height.length - 1;
let leftMax = 0, rightMax = 0;
let 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;
}
module.exports = trap;Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.