Trapping Rain Water

Asked byAmazonGoldman SachsFacebookBloombergMicrosoftGoogle

Problem

Given an array representing an elevation map where each bar has width 1, compute how much rainwater it can trap after raining.

Examples

Example 1

Input:height = [0,1,0,2,1,0,1,3,2,1,2,1]

Output:6

Example 2

Input:height = [4,2,0,3,2,5]

Output:9

Constraints

n == height.length
1 <= n <= 2 * 10^4

Solve it in the editor. Sign in free to run your Python or JavaScript against test cases, get a verdict, and track your attempts.

Solve on FeatCode →

How to approach it: the Two Pointers pattern

Two indices move through a sorted (or sortable) structure — often from opposite ends or at different speeds — to avoid the nested loops a brute-force scan would need.

Look for this pattern when

The input is sorted, or can be sorted without losing information you need.
You're looking for a pair, triplet, or partition that satisfies a sum or comparison condition.
You need to compare values from both ends of a sequence (e.g. palindrome checks).

Read the full Two Pointers guide →

Video walkthroughs

Original problem on LeetCode ↗