Trapping Rain Water LeetCode Solution (Hard) (2026)

Approach Summary

Track max height from left and right. Water at each position is min(maxLeft, maxRight) - height. Move the pointer with the smaller max.

Practice Mode

Solve it yourself before revealing the code

DSA interviews test reasoning from brute force to optimal. Think through the constraints first.

Full Solution & Approach

Water collects above a bar only when there is higher ground on both sides. The water on top of bar i is min(max height to its left, max height to its right) minus height[i]. Precomputing prefix and suffix maximums gives the answer directly in one extra pass, but the two-pointer version does it with O(1) space. Maintain leftMax and rightMax as you converge from both ends with two pointers. When leftMax is smaller, the water above the left pointer is fully determined by leftMax (rightMax can only be larger or equal), so add leftMax - height[left] and advance left, updating leftMax. Mirror on the right. The invariant that makes this safe: for the pointer on the side with the smaller running max, the other side's max is already at least as large, so the binding constraint is known.

Each bar is visited once by one of the two pointers — O(n) time. Only two running maxima and the pointers — O(1) space.

Solution Code

Solution

public int trap(int[] height) {
    if (height.length == 0) return 0;
    int left = 0, right = height.length - 1;
    int leftMax = 0, rightMax = 0, water = 0;
    while (left < right) {
        if (height[left] < height[right]) {
            leftMax = Math.max(leftMax, height[left]);
            water += leftMax - height[left];
            left++;
        } else {
            rightMax = Math.max(rightMax, height[right]);
            water += rightMax - height[right];
            right--;
        }
    }
    return water;
}

int trap(const vector<int>& height) {
    if (height.empty()) return 0;
    int left = 0, right = (int)height.size() - 1;
    int leftMax = 0, rightMax = 0, water = 0;
    while (left < right) {
        if (height[left] < height[right]) {
            leftMax = max(leftMax, height[left]);
            water += leftMax - height[left];
            left++;
        } else {
            rightMax = max(rightMax, height[right]);
            water += rightMax - height[right];
            right--;
        }
    }
    return water;
}

def trap(height: list[int]) -> int:
    if not height:
        return 0
    left, right = 0, len(height) - 1
    left_max = right_max = 0
    water = 0
    while left < right:
        if height[left] < height[right]:
            left_max = max(left_max, height[left])
            water += left_max - height[left]
            left += 1
        else:
            right_max = max(right_max, height[right])
            water += right_max - height[right]
            right -= 1
    return water

function trap(height) {
  if (!height.length) return 0;
  let left = 0, right = height.length - 1;
  let leftMax = 0, rightMax = 0;
  let water = 0;
  while (left < right) {
    if (height[left] < height[right]) {
      leftMax = Math.max(leftMax, height[left]);
      water += leftMax - height[left];
      left++;
    } else {
      rightMax = Math.max(rightMax, height[right]);
      water += rightMax - height[right];
      right--;
    }
  }
  return water;
}

Edge Cases to Watch

Monotonically increasing heights — no water at all
Flat profile with a dip — water fills the dip
Two tall towers sandwiching short bars — the classic full trap
Empty or single-element array — return 0

Algorithmic Pattern

Master the Two Pointers Pattern

View Pattern Guide →

Study the core invariant, step-by-step decision framework, and common interview traps for the Two Pointers pattern.

Framework: Two Pointers • Interview Prep: Tested at FAANG • Explore all Two Pointers problems & invariants →

How to Recognize This Pattern

Water trapped between bars
Classic two-pointer/DP hybrid

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(1)

Frequently Asked Questions

What is the optimal time and space complexity for Trapping Rain Water?

The optimal solution for Trapping Rain Water achieves O(n) runtime complexity and requires O(1) auxiliary space. Each bar is visited once by one of the two pointers — O(n) time. Only two running maxima and the pointers — O(1) space.

How do I identify that Trapping Rain Water requires the Two Pointers pattern?

In technical interviews, look for key problem signals: Water trapped between bars; Classic two-pointer/DP hybrid. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Two Pointers strategy.

What critical edge cases must be handled in Trapping Rain Water?

Essential edge cases to verify include: Monotonically increasing heights — no water at all; Flat profile with a dip — water fills the dip; Two tall towers sandwiching short bars — the classic full trap; Empty or single-element array — return 0. Always walk through these scenarios with your interviewer before coding.

Which tech companies frequently ask Trapping Rain Water?

Trapping Rain Water is a Hard-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Amazon, Google, Facebook, Apple.

Trapping Rain Water LeetCode Solution