Trapping Rain Water

Problem#

Given an array of non-negative heights, compute the total water trapped between bars after rain.

Examples#

[0,1,0,2,1,0,1,3,2,1,2,1] → 6.
[4,2,0,3,2,5] → 9.

Constraints#

1 <= n <= 2 * 10^4.

Approach#

Two pointers from both ends with running leftMax, rightMax. At each step the shorter side bounds the water there: if h[l] < h[r], water at l is leftMax - h[l]; advance l. Else mirror for r.

Solution#

class Solution {
public:
    int trap(vector<int>& h) {
        int l = 0, r = h.size() - 1;
        int leftMax = 0, rightMax = 0, total = 0;
        while (l < r) {
            if (h[l] < h[r]) {
                leftMax = max(leftMax, h[l]);
                total += leftMax - h[l];
                ++l;
            } else {
                rightMax = max(rightMax, h[r]);
                total += rightMax - h[r];
                --r;
            }
        }
        return total;
    }
};

func trap(h []int) int {
  l, r := 0, len(h)-1
  leftMax, rightMax, total := 0, 0, 0
  for l < r {
    if h[l] < h[r] {
      if h[l] > leftMax {
        leftMax = h[l]
      }
      total += leftMax - h[l]
      l++
    } else {
      if h[r] > rightMax {
        rightMax = h[r]
      }
      total += rightMax - h[r]
      r--
    }
  }
  return total
}

from typing import List

class Solution:
    def trap(self, h: List[int]) -> int:
        l, r = 0, len(h) - 1
        left_max = right_max = total = 0
        while l < r:
            if h[l] < h[r]:
                left_max = max(left_max, h[l])
                total += left_max - h[l]
                l += 1
            else:
                right_max = max(right_max, h[r])
                total += right_max - h[r]
                r -= 1
        return total

var trap = function(h) {
    let l = 0, r = h.length - 1;
    let leftMax = 0, rightMax = 0, total = 0;
    while (l < r) {
        if (h[l] < h[r]) {
            leftMax = Math.max(leftMax, h[l]);
            total += leftMax - h[l];
            l++;
        } else {
            rightMax = Math.max(rightMax, h[r]);
            total += rightMax - h[r];
            r--;
        }
    }
    return total;
};

class Solution {
    public int trap(int[] h) {
        int l = 0, r = h.length - 1;
        int leftMax = 0, rightMax = 0, total = 0;
        while (l < r) {
            if (h[l] < h[r]) {
                leftMax = Math.max(leftMax, h[l]);
                total += leftMax - h[l];
                l++;
            } else {
                rightMax = Math.max(rightMax, h[r]);
                total += rightMax - h[r];
                r--;
            }
        }
        return total;
    }
}

function trap(h: number[]): number {
    let l: number = 0, r: number = h.length - 1;
    let leftMax: number = 0, rightMax: number = 0, total: number = 0;
    while (l < r) {
        if (h[l] < h[r]) {
            leftMax = Math.max(leftMax, h[l]);
            total += leftMax - h[l];
            l++;
        } else {
            rightMax = Math.max(rightMax, h[r]);
            total += rightMax - h[r];
            r--;
        }
    }
    return total;
}

Editorial#

The key insight: if h[l] < h[r], the water level at index l is determined entirely by walls on the left side (we know a wall of height h[r] exists on the right, which is at least as tall as the left’s current cap). So we can safely commit to leftMax - h[l] water at position l and advance.

Complexity#

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

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#