☕ DSA Java Articles

Topics › Stacks and Queues › Monotonic Stack/Queue Problems [VVV. Imp]

Trapping Rainwater

Hard TUF ID 965 A2ZSDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an array height of n non-negative integers. It describes an elevation map: bar i is a column of width 1 and height height[i]. After it rains, water collects in the dips between taller bars. Return the total amount of water trapped, measured in unit squares.

Constraints (LeetCode 42): 1 ≤ n ≤ 2 × 10^4, 0 ≤ height[i] ≤ 10^5. The Java methods return a long so that they stay correct even for heights near 2 × 10^9, where the total can exceed an int.

Example 1

height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
answer = 6       // 1 unit above index 2, 4 units over indices 4-6, 1 unit above index 9

Example 2

height = [4, 2, 0, 3, 2, 5]
answer = 9       // the 4 and the 5 hold water at level 4: 2 + 4 + 1 + 2

Example 3

height = [5, 4, 1, 2]
answer = 1       // only the bar of height 1 holds water, filled up to the 2 on its right

The formula behind every approach. Look at one column i on its own. Water above it can rise only as high as the lower of two walls: the tallest bar anywhere on its left and the tallest bar anywhere on its right. Above that level the water would spill over the shorter wall. So

water[i] = min(maxLeft(i), maxRight(i)) - height[i]

where both maxima include height[i] itself. Including it means the result is never negative: a bar taller than everything on one side simply holds 0. The answer is the sum of water[i] over all columns. The four approaches below differ only in how quickly they find the two maxima.

Approach 1: Brute force

Intuition. Apply the formula literally. For each column, scan everything to its left for the tallest bar, scan everything to its right for the tallest bar, and add the difference. Each column costs a full pass over the array, so the total work is quadratic.

Algorithm.

  1. For every index i:
  2. leftMax = maximum of height[0..i], rightMax = maximum of height[i..n-1].
  3. Add min(leftMax, rightMax) - height[i] to the total.
static long bruteForce(int[] height) {
    int n = height.length;
    long water = 0;
    for (int i = 0; i < n; i++) {
        int leftMax = 0, rightMax = 0;
        for (int j = 0; j <= i; j++) leftMax = Math.max(leftMax, height[j]);
        for (int j = i; j < n; j++) rightMax = Math.max(rightMax, height[j]);
        water += Math.min(leftMax, rightMax) - height[i];
    }
    return water;
}

Complexity. Time O(n^2): each of the n columns scans n bars. Space O(1).

Every column recomputes maxima that its neighbour has just computed. Removing that repetition is the whole game.

Approach 2: Better, prefix and suffix maxima

Intuition. maxLeft(i) is a running maximum from the left, so maxLeft(i) = max(maxLeft(i - 1), height[i]). Likewise maxRight(i) = max(maxRight(i + 1), height[i]). Fill both arrays with one sweep each, then apply the formula in a third sweep.

Algorithm.

  1. If the array is empty, return 0.
  2. leftMax[0] = height[0]; for i = 1..n-1, leftMax[i] = max(leftMax[i-1], height[i]).
  3. rightMax[n-1] = height[n-1]; for i = n-2..0, rightMax[i] = max(rightMax[i+1], height[i]).
  4. Sum min(leftMax[i], rightMax[i]) - height[i].
static long prefixSuffix(int[] height) {
    int n = height.length;
    if (n == 0) return 0;
    int[] leftMax = new int[n], rightMax = new int[n];
    leftMax[0] = height[0];
    for (int i = 1; i < n; i++) leftMax[i] = Math.max(leftMax[i - 1], height[i]);
    rightMax[n - 1] = height[n - 1];
    for (int i = n - 2; i >= 0; i--) rightMax[i] = Math.max(rightMax[i + 1], height[i]);
    long water = 0;
    for (int i = 0; i < n; i++) water += Math.min(leftMax[i], rightMax[i]) - height[i];
    return water;
}

Complexity. Time O(n): three linear sweeps. Space O(n) for the two arrays.

This is the version to reach for first in an interview: it follows directly from the formula and is easy to get right.

Approach 3: Monotonic stack, filling layer by layer

Intuition. The first two approaches measure water in vertical strips, one column at a time. You can also measure it in horizontal slabs. Walk left to right and keep a stack of indices whose heights never increase from bottom to top: these are bars still waiting for a taller bar on their right to close a basin.

When height[i] is taller than the bar on top of the stack, that top bar is the bottom of a dip. Pop it. The new top is the nearest bar on the left that is at least as tall as the bottom, which is the left wall, and i is the right wall. Between them lies a rectangle of water:

Keep popping while height[i] is still taller than the top, adding one slab per pop. Each slab sits on top of the previous one, so together they fill the basin to the level of the lower wall. If the stack becomes empty after a pop, there is no left wall and that water spills away.

This is the Next Greater Element stack in disguise: a bar is popped exactly when its next greater bar to the right arrives, and the bar underneath it is its previous bar of at least the same height.

Algorithm.

  1. Create an empty stack of indices.
  2. For each i from left to right:
    • While the stack is not empty and height[i] > height[top]: pop bottom; if the stack is now empty, stop; otherwise let left be the top and add (i - left - 1) × (min(height[left], height[i]) - height[bottom]).
    • Push i.
  3. Return the total.
static long monotonicStack(int[] height) {
    long water = 0;
    Deque<Integer> st = new ArrayDeque<>();      // indices; heights never increase from bottom to top
    for (int i = 0; i < height.length; i++) {
        while (!st.isEmpty() && height[i] > height[st.peek()]) {
            int bottom = st.pop();
            if (st.isEmpty()) break;             // no wall on the left: this layer spills out
            int left = st.peek();
            long width = i - left - 1;
            long depth = Math.min(height[left], height[i]) - height[bottom];
            water += width * depth;
        }
        st.push(i);
    }
    return water;
}

Dry run on [4, 2, 0, 3, 2, 5] (stack shows indices, bottom first):

i height[i] pops and slabs added total stack after push
0 4 none 0 0
1 2 none 0 0, 1
2 0 none 0 0, 1, 2
3 3 bottom 2, left 1: width 1, depth 2 → 2; bottom 1, left 0: width 2, depth 1 → 2 4 0, 3
4 2 none 4 0, 3, 4
5 5 bottom 4, left 3: 1 × 1 → 1; bottom 3, left 0: 4 × 1 → 4; bottom 0, no left wall 9 5

Complexity. Time O(n): every index is pushed once and popped at most once. Space O(n) for the stack, for example on a falling terrain where nothing is popped.

Equal heights need no special case. In [2, 1, 1, 2] the second 1 is popped with the first 1 as its left wall, giving depth 0; the next pop then uses the left 2 as the wall and adds a slab of width 2 and depth 1.

Approach 4: Optimal, two pointers

Intuition. We do not need both maxima exactly, only the smaller of the two. Put one pointer at each end and keep leftMax, the tallest bar passed by the left pointer, and rightMax, the tallest bar passed by the right pointer.

Suppose height[l] <= height[r]. Then the right side of l certainly has a wall at least as tall as height[r]. Every bar the left pointer has passed was passed while it was no taller than some bar at or beyond the current r, so leftMax is also no taller than the true maxRight(l). That means the lower wall for column l is on its left, and its water is max(leftMax, height[l]) - height[l], known right now, without ever learning maxRight(l) exactly. Process l and move it inward. The mirror argument applies when height[r] < height[l].

The pointers meet at one of the tallest bars, which holds no water, so the loop can stop at l < r.

Algorithm.

  1. l = 0, r = n - 1, leftMax = rightMax = 0.
  2. While l < r:
    • If height[l] <= height[r]: if height[l] >= leftMax, update leftMax; otherwise add leftMax - height[l]. Then l++.
    • Otherwise do the same on the right with rightMax, then r--.
  3. Return the total.
static long optimal(int[] height) {
    int l = 0, r = height.length - 1;
    int leftMax = 0, rightMax = 0;
    long water = 0;
    while (l < r) {
        if (height[l] <= height[r]) {            // the right side has a wall at least this tall
            if (height[l] >= leftMax) leftMax = height[l];
            else water += leftMax - height[l];
            l++;
        } else {                                 // the left side has a wall taller than this
            if (height[r] >= rightMax) rightMax = height[r];
            else water += rightMax - height[r];
            r--;
        }
    }
    return water;
}

Dry run on [5, 4, 1, 2]:

l r compare action leftMax rightMax total
0 3 5 > 2 right side: 2 is a new max 0 2 0
0 2 5 > 1 right side: add 2 - 1 0 2 1
0 1 5 > 4 right side: 4 is a new max 0 4 1
0 0 stop       1

Complexity. Time O(n): each step moves one pointer one position. Space O(1).

Edge cases and pitfalls