Skip to main content
Talentd

Trapping Rain Water - Solution & Explanation

HardArrayTwo PointersDynamic ProgrammingStack20 min readAsked at: Amazon, Microsoft, Apple +70
Practice this problem

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:

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.length
  • 1 <= n <= 2 * 104
  • 0 <= 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.

This implementation uses two arrays: leftMax and rightMax to keep track of the maximum height encountered from the left and right of each bar respectively. It then calculates the trapped water by iterating through each bar and adding the minimum of these maximum heights minus the bar's height.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) because we traverse the height array three times where n is the length of the array.
Space Complexity: O(n) due to the additional arrays used to store the maximum heights.

Try this approach in the editor →

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.

This approach leverages two pointers, starting from both ends of the array and moving towards the center. It dynamically updates the maximum height seen so far from either direction and calculates water trapped at the current position based on these max heights.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the input array since we process each bar only once.
Space Complexity: O(1) because we use only constant extra space.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScriptRustC#PHP

Python

Java

C++

Go

TypeScript

Rust

C#

PHP

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Two-Pass Dynamic Programming

Time Complexity: O(n) because we traverse the height array three times where n is the length of the array.
Space Complexity: O(n) due to the additional arrays used to store the maximum heights.

Two-Pointer Technique

Time Complexity: O(n), where n is the length of the input array since we process each bar only once.
Space Complexity: O(1) because we use only constant extra space.

Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Two-Pass Dynamic ProgrammingO(n)O(n)When clarity matters and extra memory is acceptable
Two-Pointer TechniqueO(n)O(1)Optimal interview solution with constant extra space
Monotonic StackO(n)O(n)Useful when learning stack-based boundary detection

Video Solution

Trapping Rain Water - Google Interview Question - Leetcode 42 • NeetCode • 770,013 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Trapping Rain Water with our built-in code editor and test cases.

Practice on FleetCode
Previous

Container With Most Water

Next

Maximum Value of an Ordered Triplet II