Problem editorial

Trapping Rain Water

HardTwo PointersArrayTwo PointersPointers

Editorial

Core insight

Trapping Rain Water · Two Pointers

Core Insight for Trapping Rain Water

The direct formula for a position is:

text

water[i] = min(tallest bar to the left, tallest bar to the right) - height[i]

Computing both maxima independently for every index causes the brute force O(n²) complexity. The two-pointer approach avoids repeated scans by maintaining the highest boundary already seen from each side:

leftMax: maximum height encountered while moving from the left.
rightMax: maximum height encountered while moving from the right.

At any point:

If height[left] <= height[right], the left position can be finalized.
Otherwise, the right position can be finalized.

When the current left bar is no taller than the current right bar, the right side already provides a boundary at least as high as height[left]. Therefore, the amount of water at the left position is determined by leftMax. The symmetric argument applies when processing the right side.

The key invariant is:

Every position removed from the active range has enough information to determine its trapped water using the maximum boundary maintained on its own side and the current bar on the opposite side.

Visual Description

The algorithm maintains an active interval [left, right]. The interval shrinks by moving exactly one pointer per iteration:

A left-side transition updates leftMax and moves left one position right.
A right-side transition updates rightMax and moves right one position left.
The accumulated water records finalized contributions outside the remaining interval.

The visual state changes are therefore represented by two boundary markers converging toward the center, while two running maximum values summarize the processed portions of the array.

In-place Array Modification Pattern Visualization for LeetCode 42: Trapping Rain Water

Deep dive

Full breakdown

Full reasoning, pitfalls, and implementation flow

LeetCode 42: Trapping Rain Water Solution & Explanation

Problem Overview

TL;DR: Use two pointers with leftMax and rightMax, always process the side with the smaller current bar because its trapped water is already bounded by the opposite pointer.

The LeetCode 42 Solution must calculate the total water trapped between adjacent bars of different heights. For each position, the possible water level depends on the tallest bar to its left and the tallest bar to its right. The water above that position is limited by the shorter of those two boundaries.

In LeetCode 42: Trapping Rain Water, the goal is to return the total trapped water without modifying the required method signature. Because the input length can reach 20,000, an optimal solution for interviews should run in linear time.

Brute Force Approach for Trapping Rain Water

For every bar at index i, independently search:

The tallest bar from index 0 through i.
The tallest bar from index i through the final index.
The water above i:

text

waterAtI = min(leftMaximum, rightMaximum) - height[i]

If the result is negative, no water is trapped at that position.

Naive Pseudocode

text

totalWater = 0

for i from 0 to n - 1:
    leftMaximum = 0
    rightMaximum = 0

    for j from 0 to i:
        leftMaximum = max(leftMaximum, height[j])

    for j from i to n - 1:
        rightMaximum = max(rightMaximum, height[j])

    trapped = min(leftMaximum, rightMaximum) - height[i]

    if trapped > 0:
        totalWater += trapped

return totalWater

Complexity

Time: O(n²), because two scans may be performed for every position.
Space: O(1) auxiliary space.

With n = 20,000, an O(n²) approach may perform hundreds of millions of operations. This can result in Time Limit Exceeded, which is why the brute force method is unsuitable for the given constraints.

Algorithm Strategy: Two Pointers

Initialize left at the first index and right at the last index.
Initialize leftMax, rightMax, and water to zero.
While left < right:
- If height[left] <= height[right], process the left position.
- Otherwise, process the right position.
When processing the left position:
- Update leftMax if the current bar is taller.
- Otherwise, add leftMax - height[left] to water.
- Move left forward.
When processing the right position:
- Update rightMax if the current bar is taller.
- Otherwise, add rightMax - height[right] to water.
- Move right backward.
Return the accumulated water.

No input values are changed. The array is read while the two pointers move inward, and only constant-size state is maintained.

Execution Flow

For height = [3,0,2,0,4]:

left points to height 3, and right points to height 4.
Since 3 <= 4, process the left side:
- leftMax becomes 3.
- Move left to the bar of height 0.
The current left height 0 is still no greater than the right height 4:
- Add 3 - 0 = 3.
- Move left to height 2.
Since 2 <= 4:
- Add 3 - 2 = 1.
- Move left to height 0.
Since 0 <= 4:
- Add 3 - 0 = 3.
- Move left to the final bar.
The total is 3 + 1 + 3 = 7.

The pointer decision ensures that each processed side has a boundary sufficient to finalize its current water contribution.

Proof of Correctness

Consider an iteration where height[left] <= height[right].

The current right bar itself is a boundary at least as high as height[left]. Therefore, the maximum height on the right side is also at least height[left]. The water above left is consequently limited by the left-side maximum:

text

water[left] = max(0, leftMax - height[left])

If height[left] >= leftMax, the current bar becomes the new left boundary and traps no water. Otherwise, the difference leftMax - height[left] is exactly the trapped amount.

The case where height[right] < height[left] is symmetric. The current left bar provides a sufficient boundary for finalizing the right position, so the right-side maximum determines its trapped water.

At every step, the algorithm finalizes exactly one position whose water amount is already determined, preserves the maximum boundary for the processed side, and moves the corresponding pointer inward. Every index is processed once, so all positions are eventually finalized with their correct contribution. Therefore, the returned total is correct.

Pattern Reuse Notes

The following problems share the same pattern/subpattern:

In each problem, pointer movement processes or compacts the array while maintaining a small amount of state instead of creating a separate result structure. The exact condition and state differ, but the shared idea is linear traversal with controlled in-place or constant-space updates.

Feynman coach · Before you peek at the code

Can you explain the core insight in your own words?

If you can explain it before reading code, you’re far more likely to recall it under interview pressure.

Loading your attempt…

Reference Implementation

C++ Solution for LeetCode 42

cpp

1class Solution {
2public:
3    int trap(vector<int>& height) {
4        int left = 0;
5        int right = static_cast<int>(height.size()) - 1;
6        long long leftMax = 0;
7        long long rightMax = 0;
8        long long water = 0;
9
10        while (left < right) {
11            if (height[left] <= height[right]) {
12                if (height[left] >= leftMax) {
13                    leftMax = height[left];
14                } else {
15                    water += leftMax - height[left];
16                }
17                ++left;
18            } else {
19                if (height[right] >= rightMax) {
20                    rightMax = height[right];
21                } else {
22                    water += rightMax - height[right];
23                }
24                --right;
25            }
26        }
27
28        return static_cast<int>(water);
29    }
30};

Java Solution for LeetCode 42

java

1class Solution {
2    public int trap(int[] height) {
3        int left = 0, right = height.length - 1;
4        int leftMax = 0, rightMax = 0;
5        int water = 0;
6
7        while (left < right) {
8            if (height[left] <= height[right]) {
9                if (height[left] >= leftMax) {
10                    leftMax = height[left];
11                } else {
12                    water += leftMax - height[left];
13                }
14                left++;
15            } else {
16                if (height[right] >= rightMax) {
17                    rightMax = height[right];
18                } else {
19                    water += rightMax - height[right];
20                }
21                right--;
22            }
23        }
24
25        return water;
26    }
27}

Python Solution for LeetCode 42

python

1from typing import List, Optional
2
3class Solution:
4    def trap(self, height: List[int]) -> int:
5        left, right = 0, len(height) - 1
6        left_max = right_max = 0
7        water = 0
8
9        while left < right:
10            if height[left] <= height[right]:
11                if height[left] >= left_max:
12                    left_max = height[left]
13                else:
14                    water += left_max - height[left]
15                left += 1
16            else:
17                if height[right] >= right_max:
18                    right_max = height[right]
19                else:
20                    water += right_max - height[right]
21                right -= 1
22
23        return water

AI Coach Insight

For Trapping Rain Water, focus on explaining why the structure works, not just naming Two Pointers.

Complexity Analysis

Time: O(n)

Each pointer moves only inward, and every array position is processed at most once.
Space: O(1)

The algorithm uses only the two pointers, two maximum values, and the running total. It does not allocate another array or modify the input.

Related Patterns

Pattern: Two Pointers
Subpattern: In-place Array Modification

This problem directly fits the Two Pointers pattern: one pointer starts at the left boundary and one starts at the right boundary, and each pointer moves inward exactly once.

The supplied subpattern, In-place Array Modification, is only a loose taxonomy match here. The verified implementation does not modify the input array. Instead, it maintains constant auxiliary state—leftMax, rightMax, and the running water total—while narrowing the active range in place through pointer movement.

Common Mistakes & FAQ

Q1. Why does the naive solution TLE?

The brute force method recomputes the tallest bar on both sides for every index. This creates O(n²) time complexity. With up to 20,000 bars, the repeated scans can require too many operations and lead to Time Limit Exceeded.

The conceptual gap is failing to reuse information from earlier scans. The two-pointer solution stores the highest processed boundary in leftMax and rightMax, reducing the total work to O(n).

Q2. Why can the algorithm process the shorter current side?

A common mistake is to assume that both sides must be fully scanned before any water can be calculated.

If height[left] <= height[right], the current right bar already gives a boundary at least as high as the current left bar. Therefore, the left position's limiting boundary is known from leftMax, and the position can be finalized immediately.

Processing the taller side instead can use incomplete boundary information and produce incorrect water amounts.

Q3. Why must `leftMax` and `rightMax` be updated before calculating water?

When a current bar is at least as tall as the maximum boundary on its side, it becomes the new boundary and cannot hold water above itself. The algorithm must update the maximum first and avoid adding a negative amount.

If the update order is incorrect, the implementation may calculate water using an outdated boundary or add an invalid negative contribution.

Q4. Why should the loop condition be `left < right`?

The algorithm processes positions while the two boundaries are distinct. When left == right, there is no bar between two separate boundaries that can contribute additional water.

Using an incorrect condition can cause the center position to be processed twice or can lead to an out-of-bounds access after one pointer crosses the other.

Q5. Why is extra per-index storage unnecessary?

Arrays such as leftMaxAt[i] and rightMaxAt[i] can solve the problem, but they require O(n) additional space. The two-pointer invariant allows each position to be finalized as the active range shrinks, so only the current maximum from each side is needed.

Allocating these arrays is not a correctness error, but it misses the constant-space advantage expected from the Two Pointers pattern.

Practise Trapping Rain Water and the problems around it

Trapping Rain Water is a Two Pointers problem, in the In-place Array Modification subpattern. Once the approach above makes sense, write it yourself and then work through the neighbouring problems that reuse it.

Core insight

Trapping Rain Water · Two Pointers

Core Insight for Trapping Rain Water

The direct formula for a position is:

text

water[i] = min(tallest bar to the left, tallest bar to the right) - height[i]

leftMax: maximum height encountered while moving from the left.
rightMax: maximum height encountered while moving from the right.

At any point:

If height[left] <= height[right], the left position can be finalized.
Otherwise, the right position can be finalized.

The key invariant is:

Every position removed from the active range has enough information to determine its trapped water using the maximum boundary maintained on its own side and the current bar on the opposite side.

Visual Description

The algorithm maintains an active interval [left, right]. The interval shrinks by moving exactly one pointer per iteration:

A left-side transition updates leftMax and moves left one position right.
A right-side transition updates rightMax and moves right one position left.
The accumulated water records finalized contributions outside the remaining interval.

The visual state changes are therefore represented by two boundary markers converging toward the center, while two running maximum values summarize the processed portions of the array.

In-place Array Modification Pattern Visualization for LeetCode 42: Trapping Rain Water

Deep dive

Full breakdown

Full reasoning, pitfalls, and implementation flow

LeetCode 42: Trapping Rain Water Solution & Explanation

Problem Overview

TL;DR: Use two pointers with leftMax and rightMax, always process the side with the smaller current bar because its trapped water is already bounded by the opposite pointer.

Brute Force Approach for Trapping Rain Water

For every bar at index i, independently search:

The tallest bar from index 0 through i.
The tallest bar from index i through the final index.
The water above i:

text

waterAtI = min(leftMaximum, rightMaximum) - height[i]

If the result is negative, no water is trapped at that position.

Naive Pseudocode

text

totalWater = 0

for i from 0 to n - 1:
    leftMaximum = 0
    rightMaximum = 0

    for j from 0 to i:
        leftMaximum = max(leftMaximum, height[j])

    for j from i to n - 1:
        rightMaximum = max(rightMaximum, height[j])

    trapped = min(leftMaximum, rightMaximum) - height[i]

    if trapped > 0:
        totalWater += trapped

return totalWater

Complexity

Time: O(n²), because two scans may be performed for every position.
Space: O(1) auxiliary space.

Algorithm Strategy: Two Pointers

Initialize left at the first index and right at the last index.
Initialize leftMax, rightMax, and water to zero.
While left < right:
- If height[left] <= height[right], process the left position.
- Otherwise, process the right position.
When processing the left position:
- Update leftMax if the current bar is taller.
- Otherwise, add leftMax - height[left] to water.
- Move left forward.
When processing the right position:
- Update rightMax if the current bar is taller.
- Otherwise, add rightMax - height[right] to water.
- Move right backward.
Return the accumulated water.

No input values are changed. The array is read while the two pointers move inward, and only constant-size state is maintained.

Execution Flow

For height = [3,0,2,0,4]:

left points to height 3, and right points to height 4.
Since 3 <= 4, process the left side:
- leftMax becomes 3.
- Move left to the bar of height 0.
The current left height 0 is still no greater than the right height 4:
- Add 3 - 0 = 3.
- Move left to height 2.
Since 2 <= 4:
- Add 3 - 2 = 1.
- Move left to height 0.
Since 0 <= 4:
- Add 3 - 0 = 3.
- Move left to the final bar.
The total is 3 + 1 + 3 = 7.

The pointer decision ensures that each processed side has a boundary sufficient to finalize its current water contribution.

Proof of Correctness

Consider an iteration where height[left] <= height[right].

text

water[left] = max(0, leftMax - height[left])

If height[left] >= leftMax, the current bar becomes the new left boundary and traps no water. Otherwise, the difference leftMax - height[left] is exactly the trapped amount.

Pattern Reuse Notes

The following problems share the same pattern/subpattern:

Feynman coach · Before you peek at the code

Can you explain the core insight in your own words?

If you can explain it before reading code, you’re far more likely to recall it under interview pressure.

Loading your attempt…

Reference Implementation

C++ Solution for LeetCode 42

cpp

1class Solution {
2public:
3    int trap(vector<int>& height) {
4        int left = 0;
5        int right = static_cast<int>(height.size()) - 1;
6        long long leftMax = 0;
7        long long rightMax = 0;
8        long long water = 0;
9
10        while (left < right) {
11            if (height[left] <= height[right]) {
12                if (height[left] >= leftMax) {
13                    leftMax = height[left];
14                } else {
15                    water += leftMax - height[left];
16                }
17                ++left;
18            } else {
19                if (height[right] >= rightMax) {
20                    rightMax = height[right];
21                } else {
22                    water += rightMax - height[right];
23                }
24                --right;
25            }
26        }
27
28        return static_cast<int>(water);
29    }
30};

Java Solution for LeetCode 42

java

1class Solution {
2    public int trap(int[] height) {
3        int left = 0, right = height.length - 1;
4        int leftMax = 0, rightMax = 0;
5        int water = 0;
6
7        while (left < right) {
8            if (height[left] <= height[right]) {
9                if (height[left] >= leftMax) {
10                    leftMax = height[left];
11                } else {
12                    water += leftMax - height[left];
13                }
14                left++;
15            } else {
16                if (height[right] >= rightMax) {
17                    rightMax = height[right];
18                } else {
19                    water += rightMax - height[right];
20                }
21                right--;
22            }
23        }
24
25        return water;
26    }
27}

Python Solution for LeetCode 42

python

1from typing import List, Optional
2
3class Solution:
4    def trap(self, height: List[int]) -> int:
5        left, right = 0, len(height) - 1
6        left_max = right_max = 0
7        water = 0
8
9        while left < right:
10            if height[left] <= height[right]:
11                if height[left] >= left_max:
12                    left_max = height[left]
13                else:
14                    water += left_max - height[left]
15                left += 1
16            else:
17                if height[right] >= right_max:
18                    right_max = height[right]
19                else:
20                    water += right_max - height[right]
21                right -= 1
22
23        return water

Core Insight for Trapping Rain Water

Visual Description

LeetCode 42: Trapping Rain Water Solution & Explanation

Problem Overview

Brute Force Approach for Trapping Rain Water

Naive Pseudocode

Complexity

Algorithm Strategy: Two Pointers

Execution Flow

Proof of Correctness

Pattern Reuse Notes

Can you explain the core insight in your own words?

Reference Implementation

C++ Solution for LeetCode 42

Java Solution for LeetCode 42

Python Solution for LeetCode 42

Practise Trapping Rain Water and the problems around it

Related problems

Core Insight for Trapping Rain Water

Visual Description

LeetCode 42: Trapping Rain Water Solution & Explanation

Problem Overview

Brute Force Approach for Trapping Rain Water

Naive Pseudocode

Complexity

Algorithm Strategy: Two Pointers

Execution Flow

Proof of Correctness

Pattern Reuse Notes

Can you explain the core insight in your own words?

Reference Implementation

C++ Solution for LeetCode 42

Java Solution for LeetCode 42

Python Solution for LeetCode 42

Practise Trapping Rain Water and the problems around it

Related problems