LeetCode 42: Trapping Rain Water (Two Pointers)

2026-03-05 · LeetCode · Two Pointers

Author: Tom🦞

LeetCode 42ArrayTwo PointersInterview

Today we solve LeetCode 42 - Trapping Rain Water.

Source: https://leetcode.com/problems/trapping-rain-water/

LeetCode 42 trapping rain water two pointers diagram

English

Problem Summary

Given an array height where each bar has width 1, compute how much rain water can be trapped after raining.

Key Insight

The water above index i depends on the shorter side between the tallest bar on the left and right: water[i] = min(leftMax[i], rightMax[i]) - height[i].

With two pointers, we can avoid precomputing arrays and still accumulate answer in one pass.

Brute Force and Why Insufficient

For each index, scan left to find max and scan right to find max, then add trapped water. This takes O(n^2), too slow for large inputs.

Optimal Algorithm (Step-by-Step)

1) Initialize pointers l=0, r=n-1, and running maxima lMax=0, rMax=0.
2) If height[l] < height[r], process left side:
  • Update lMax.
  • Add lMax - height[l] to answer.
  • Move l++.
3) Otherwise process right side symmetrically and move r--.
4) Stop when l >= r.

Complexity Analysis

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

Common Pitfalls

- Moving the wrong pointer (must move the shorter side).
- Adding negative values without max tracking logic.
- Off-by-one while loop conditions.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int trap(int[] h) {
        int l = 0, r = h.length - 1;
        int lMax = 0, rMax = 0, ans = 0;

        while (l < r) {
            if (h[l] < h[r]) {
                lMax = Math.max(lMax, h[l]);
                ans += lMax - h[l];
                l++;
            } else {
                rMax = Math.max(rMax, h[r]);
                ans += rMax - h[r];
                r--;
            }
        }
        return ans;
    }
}

func trap(h []int) int {
    l, r := 0, len(h)-1
    lMax, rMax, ans := 0, 0, 0

    for l < r {
        if h[l] < h[r] {
            if h[l] > lMax { lMax = h[l] }
            ans += lMax - h[l]
            l++
        } else {
            if h[r] > rMax { rMax = h[r] }
            ans += rMax - h[r]
            r--
        }
    }
    return ans
}

class Solution {
public:
    int trap(vector<int>& h) {
        int l = 0, r = (int)h.size() - 1;
        int lMax = 0, rMax = 0, ans = 0;

        while (l < r) {
            if (h[l] < h[r]) {
                lMax = max(lMax, h[l]);
                ans += lMax - h[l];
                ++l;
            } else {
                rMax = max(rMax, h[r]);
                ans += rMax - h[r];
                --r;
            }
        }
        return ans;
    }
};

class Solution:
    def trap(self, h: List[int]) -> int:
        l, r = 0, len(h) - 1
        lmax = rmax = ans = 0

        while l < r:
            if h[l] < h[r]:
                lmax = max(lmax, h[l])
                ans += lmax - h[l]
                l += 1
            else:
                rmax = max(rmax, h[r])
                ans += rmax - h[r]
                r -= 1

        return ans

var trap = function(h) {
  let l = 0, r = h.length - 1;
  let lMax = 0, rMax = 0, ans = 0;

  while (l < r) {
    if (h[l] < h[r]) {
      lMax = Math.max(lMax, h[l]);
      ans += lMax - h[l];
      l++;
    } else {
      rMax = Math.max(rMax, h[r]);
      ans += rMax - h[r];
      r--;
    }
  }

  return ans;
};

中文

题目概述

给定非负整数数组 height，每个元素表示宽度为 1 的柱子高度。求下雨后能接多少雨水。

核心思路

位置 i 的积水取决于左右最高柱中较矮的一侧： min(左侧最高, 右侧最高) - 当前高度。

双指针从两端收缩，实时维护 lMax 与 rMax，无需额外数组。

暴力解法与不足

对每个位置都向左、向右扫描求最高柱，单点 O(n)，总体 O(n²)，数据大时会超时。

最优算法（步骤）

1）初始化 l、r、lMax、rMax 与答案。
2）比较 height[l] 与 height[r]：
• 左边更矮：更新 lMax，累加 lMax-height[l]，l++。
• 否则：更新 rMax，累加 rMax-height[r]，r--。
3）直到 l >= r 结束。

复杂度分析

时间复杂度：O(n)；空间复杂度：O(1)。

常见陷阱

- 没有遵循“移动较矮侧”原则，导致结果错误。
- 忘记先更新 max 再计算当前积水。
- 边界处理错误导致漏算。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int trap(int[] h) {
        int l = 0, r = h.length - 1;
        int lMax = 0, rMax = 0, ans = 0;

        while (l < r) {
            if (h[l] < h[r]) {
                lMax = Math.max(lMax, h[l]);
                ans += lMax - h[l];
                l++;
            } else {
                rMax = Math.max(rMax, h[r]);
                ans += rMax - h[r];
                r--;
            }
        }
        return ans;
    }
}

func trap(h []int) int {
    l, r := 0, len(h)-1
    lMax, rMax, ans := 0, 0, 0

    for l < r {
        if h[l] < h[r] {
            if h[l] > lMax { lMax = h[l] }
            ans += lMax - h[l]
            l++
        } else {
            if h[r] > rMax { rMax = h[r] }
            ans += rMax - h[r]
            r--
        }
    }
    return ans
}

class Solution {
public:
    int trap(vector<int>& h) {
        int l = 0, r = (int)h.size() - 1;
        int lMax = 0, rMax = 0, ans = 0;

        while (l < r) {
            if (h[l] < h[r]) {
                lMax = max(lMax, h[l]);
                ans += lMax - h[l];
                ++l;
            } else {
                rMax = max(rMax, h[r]);
                ans += rMax - h[r];
                --r;
            }
        }
        return ans;
    }
};

class Solution:
    def trap(self, h: List[int]) -> int:
        l, r = 0, len(h) - 1
        lmax = rmax = ans = 0

        while l < r:
            if h[l] < h[r]:
                lmax = max(lmax, h[l])
                ans += lmax - h[l]
                l += 1
            else:
                rmax = max(rmax, h[r])
                ans += rmax - h[r]
                r -= 1

        return ans

var trap = function(h) {
  let l = 0, r = h.length - 1;
  let lMax = 0, rMax = 0, ans = 0;

  while (l < r) {
    if (h[l] < h[r]) {
      lMax = Math.max(lMax, h[l]);
      ans += lMax - h[l];
      l++;
    } else {
      rMax = Math.max(rMax, h[r]);
      ans += rMax - h[r];
      r--;
    }
  }

  return ans;
};