How do you approach Trapping Rain Water?

For each position, water trapped = min(maxLeft, maxRight) - height[i].

What is the time complexity of Trapping Rain Water?

Time complexity: O(n). Space complexity: O(1).

What are common mistakes on Trapping Rain Water?

Forgetting the input has to be sorted. If it is not, the pointer moves mean nothing and the answer only looks right on the sample. Moving both pointers on a match when only one should move, which steps over valid pairs. Choosing left < right where left <= right is meant. The first never examines the middle element.

gitGood.dev

← Back to problems

Trapping Rain Water

HardAlgorithms

Description

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 elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water are being trapped.

Example 2

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

Output: 9

Constraints

- n == height.length - 1 <= n <= 2 * 10^4 - 0 <= height[i] <= 10^5

Trapping Rain Water: approach, complexity and pitfalls

A hard two pointers problem, graded against 6 test cases (3 of them hidden).

The pattern: Two Pointers

Two indices walking a sorted array or string, usually from opposite ends.

Reach for it when you see: A sorted input, a palindrome check, or a pair/triplet that must satisfy a condition.

If you are stuck

Show the 3-step hint ladder

For each position, water trapped = min(maxLeft, maxRight) - height[i].
Use two pointers from both ends.
Process the side with the smaller max height.

The optimal approach

Show the approach: Two Pointers

Use two pointers from both ends. At each step, process the side with the smaller max height. Water at that position is limited by that smaller max.

Time: O(n)
Space: O(1)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Two Pointers mistakes

These apply to the pattern as a whole, not just this problem.

Forgetting the input has to be sorted. If it is not, the pointer moves mean nothing and the answer only looks right on the sample.
Moving both pointers on a match when only one should move, which steps over valid pairs.
Choosing `left < right` where `left <= right` is meant. The first never examines the middle element.