💬 Discord
Sign In
NeetCode #218LC-42HardTwo PointersNC 150NC 250
← Back to All Problems

#218 · #42 · Trapping Rain Water(接雨水)

📌 Problem Statement & Constraints

Given n non-negative integers representing an elevation map where each bar has width 1, compute how much water it can trap after raining. Constraints: 1 <= n <= 2 * 10^4, 0 <= height[i] <= 10^5.

💡 Core Algorithmic Approaches

  1. The water above bar i is min(max_left, max_right) - height[i], where the maxima exclude i itself.
  2. The straightforward solution precomputes prefix maxima and suffix maxima, giving O(n) time and O(n) space.
  3. Two-pointer refinement: maintain left_max and right_max while closing in from both ends. When left_max < right_max, the water at the left pointer is fully determined by left_max, so it can be settled immediately.
  4. This reduces the extra space to O(1) while keeping O(n) time.

💻 Benchmark Python3 Implementation

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0
        i, j = 0, len(height) - 1
        left_max = right_max = 0
        water = 0
        while i < j:
            left_max = max(left_max, height[i])
            right_max = max(right_max, height[j])
            if left_max < right_max:
                # the left bar is the limiting side -> its water is final
                water += left_max - height[i]
                i += 1
            else:
                water += right_max - height[j]
                j -= 1
        return water


# Prefix/suffix maxima variant: O(n) space, easier to reason about
class Solution2:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        if n == 0:
            return 0
        left = [0] * n
        right = [0] * n
        left[0] = height[0]
        for i in range(1, n):
            left[i] = max(left[i - 1], height[i])
        right[n - 1] = height[n - 1]
        for i in range(n - 2, -1, -1):
            right[i] = max(right[i + 1], height[i])
        return sum(min(left[i], right[i]) - height[i] for i in range(n))

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass with two pointers, or two passes plus a sum for the prefix variant.
💾 Space Complexity
O(1) for the two-pointer version, O(n) for the prefix/suffix arrays.

⚠️ Interview Pitfalls & Follow-ups

  • Including height[i] in its own maxima: the water at a bar depends on the tallest bars strictly to either side, but taking max(left_max, height[i]) is actually fine because the resulting term is left_max - height[i] >= 0. The subtle point is that you must update the maxima before adding the water, or negative contributions appear.
  • Adding water before updating the maxima: with left_max initialised to 0, the first bar would contribute a negative amount.
  • Assuming the two-pointer choice is arbitrary: the correctness relies on settling the side with the smaller maximum, because the other side already guarantees at least that much water.
  • Using <= in the branch: ties can go either way, but exactly one branch must execute per iteration.