#76 · Two Pointers

Trapping Rain Water

Given n non-negative integers representing an elevation map where each bar has width 1, compute how much water it can trap after raining.

HardLeetCode

Active
Found
Window
Visited
Rejected

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Water level per bar

Water above bar i rises to the lower of the tallest bars on its left and on its right, minus the height of the bar itself: min(leftMax(i), rightMax(i)) − height[i]. Summing this over all bars gives the answer.

Memory layout

A single array of heights; the maxima can be arrays, a stack, or two running numbers.

Operation	Cost
prefix + suffix arrays	O(n) time, O(n) space
two pointers	O(n) time, O(1) space

Monotonic stack

A stack of indices with decreasing heights. A taller bar closes pools on top of the bars it pops: for each popped floor the left wall is the new top of the stack and the right wall is the current bar, so one horizontal layer is counted per pop.

Memory layout

A stack of at most n indices.

Operation	Cost
time / space	O(n) / O(n)

Why it fits

The depth of water at a bar depends only on two numbers, the tallest bar to its left and the tallest to its right, so everything reduces to computing those two maxima efficiently.
Prefix and suffix maxima are classic running aggregates: one forward and one backward pass. Two pointers go further and note that only the SMALLER side's maximum matters at each step.
A stack counts water layer by layer in the order pools close, matching how a physical pool fills between two walls.

Why alternatives degrade

Counting only local dips:: A pool can be wider than a single dip (like the one between bars 3 and 7 here); local comparisons with neighbours miss it.
Greedy from the tallest bar only:: It splits the problem at the global maximum, which is valid (two scans towards the middle), but needs a first pass to find that maximum; two pointers do it without the pre-pass.
Sorting the bars:: Position matters: water depends on which bars are adjacent, which sorting destroys.

Four approaches, from naive to production

1 · beginner

Scan both sides for every bar

time O(n²)space O(1)

For each bar, scan to the left for the tallest bar and to the right for the tallest bar, and add min(left, right) − height to the total.

int trap(vector<int>& height) {
    int water = 0;
    int n = height.size();
    for (int i = 0; i < n; i++) {
        int leftMax = 0, rightMax = 0;
        for (int j = 0; j <= i; j++) leftMax = max(leftMax, height[j]);
        for (int j = i; j < n; j++) rightMax = max(rightMax, height[j]);
        water += min(leftMax, rightMax) - height[i];
    }
    return water;
}

public int trap(int[] height) {
    int water = 0;
    int n = height.length;
    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;
}

def trap(height):
    water = 0
    n = len(height)
    for i in range(n):
        left_max = right_max = 0
        for j in range(i + 1): left_max = max(left_max, height[j])
        for j in range(i, n): right_max = max(right_max, height[j])
        water += min(left_max, right_max) - height[i]
    return water

function trap(height: number[]): number {
  let water = 0;
  for (let i = 0; i < height.length; i++) {
    let leftMax = 0, rightMax = 0;
    for (let j = 0; j <= i; j++) leftMax = Math.max(leftMax, height[j]);
    for (let j = i; j < height.length; j++) rightMax = Math.max(rightMax, height[j]);
    water += Math.min(leftMax, rightMax) - height[i];
  }
  return water;
}

Flaws & bottlenecks

Rescans the same ranges for every bar: quadratic.
The two maxima of neighbouring bars differ only by one element, yet are recomputed in full.
Too slow for n = 20,000 or more.

Interviewer cross-questions

Why is water above a bar min(leftMax, rightMax) − height?

Say: Water spills over the lower of the two walls, so its level equals the lower wall. The bar itself occupies height[i] of that depth.

Can the result be negative?

Say: No: leftMax and rightMax both include the bar itself, so min(leftMax, rightMax) ≥ height[i].

How do you avoid the repeated scans?

Say: Precompute prefix maxima and suffix maxima, or track running maxima with two pointers.

2 · intermediate

Prefix and suffix maximum arrays

time O(n)space O(n)

Fill leftMax[i] with a forward pass and rightMax[i] with a backward pass, then add min(leftMax[i], rightMax[i]) − height[i] for every bar.

int trap(vector<int>& height) {
    int n = height.size();
    if (n == 0) return 0;
    vector<int> left(n), right(n);
    left[0] = height[0];
    for (int i = 1; i < n; i++) left[i] = max(left[i - 1], height[i]);
    right[n - 1] = height[n - 1];
    for (int i = n - 2; i >= 0; i--) right[i] = max(right[i + 1], height[i]);
    int water = 0;
    for (int i = 0; i < n; i++) water += min(left[i], right[i]) - height[i];
    return water;
}

public int trap(int[] height) {
    int n = height.length;
    if (n == 0) return 0;
    int[] left = new int[n], right = new int[n];
    left[0] = height[0];
    for (int i = 1; i < n; i++) left[i] = Math.max(left[i - 1], height[i]);
    right[n - 1] = height[n - 1];
    for (int i = n - 2; i >= 0; i--) right[i] = Math.max(right[i + 1], height[i]);
    int water = 0;
    for (int i = 0; i < n; i++) water += Math.min(left[i], right[i]) - height[i];
    return water;
}

def trap(height):
    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])
    water = 0
    for i in range(n): water += min(left[i], right[i]) - height[i]
    return water

function trap(height: number[]): number {
  const n = height.length;
  if (n === 0) return 0;
  const left = new Array<number>(n), right = new Array<number>(n);
  left[0] = height[0];
  for (let i = 1; i < n; i++) left[i] = Math.max(left[i - 1], height[i]);
  right[n - 1] = height[n - 1];
  for (let i = n - 2; i >= 0; i--) right[i] = Math.max(right[i + 1], height[i]);
  let water = 0;
  for (let i = 0; i < n; i++) water += Math.min(left[i], right[i]) - height[i];
  return water;
}

Flaws & bottlenecks

Two extra arrays of length n.
Three passes over the data.
The empty-input case needs its own guard (left[0] would not exist).

Interviewer cross-questions

Why does leftMax[i] depend only on leftMax[i − 1]?

Say: The maximum of the first i + 1 bars is the larger of the maximum of the first i bars and the new bar.

Can you save one of the arrays?

Say: Yes: compute the right maxima into an array, then walk left to right keeping leftMax in a variable. Two pointers remove both arrays.

What is the memory cost for a million bars?

Say: Two arrays of a million integers (8 MB with 32-bit ints), which two pointers avoid.

3 · advanced

Monotonic stack, one layer per pop

time O(n)space O(n)

Keep a stack of indices with decreasing heights. When a bar is taller than the top, pop the top as the pool floor; the new top is the left wall and the current bar the right wall. Add width × depth for that layer.

int trap(vector<int>& height) {
    vector<int> stack;
    int water = 0;
    for (int i = 0; i < (int)height.size(); i++) {
        while (!stack.empty() && height[i] > height[stack.back()]) {
            int bottom = stack.back(); stack.pop_back();
            if (stack.empty()) break;
            int left = stack.back();
            int width = i - left - 1;
            int bounded = min(height[left], height[i]) - height[bottom];
            water += width * bounded;
        }
        stack.push_back(i);
    }
    return water;
}

public int trap(int[] height) {
    Deque<Integer> stack = new ArrayDeque<>();
    int water = 0;
    for (int i = 0; i < height.length; i++) {
        while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
            int bottom = stack.pop();
            if (stack.isEmpty()) break;
            int left = stack.peek();
            int width = i - left - 1;
            int bounded = Math.min(height[left], height[i]) - height[bottom];
            water += width * bounded;
        }
        stack.push(i);
    }
    return water;
}

def trap(height):
    stack = []
    water = 0
    for i in range(len(height)):
        while stack and height[i] > height[stack[-1]]:
            bottom = stack.pop()
            if not stack: break
            left = stack[-1]
            width = i - left - 1
            bounded = min(height[left], height[i]) - height[bottom]
            water += width * bounded
        stack.append(i)
    return water

function trap(height: number[]): number {
  const stack: number[] = [];
  let water = 0;
  for (let i = 0; i < height.length; i++) {
    while (stack.length > 0 && height[i] > height[stack[stack.length - 1]]) {
      const bottom = stack.pop()!;
      if (stack.length === 0) break;
      const left = stack[stack.length - 1];
      const width = i - left - 1;
      const bounded = Math.min(height[left], height[i]) - height[bottom];
      water += width * bounded;
    }
    stack.push(i);
  }
  return water;
}

Flaws & bottlenecks

Needs O(n) stack space.
The layer-by-layer counting is harder to see than the per-bar formula.
Equal heights need care: a bar equal to the top is not popped, which is fine because the pool above it has zero depth.

Interviewer cross-questions

Why is each bar pushed and popped at most once?

Say: Every iteration pushes the current index, and pops only remove indices that were pushed earlier, so the total number of pops is at most n.

Why is no water counted when the stack becomes empty?

Say: Water needs a wall on both sides. If nothing remains under the popped bar there is no left wall, so it cannot hold water.

How does this relate to Largest Rectangle in Histogram?

Say: Both use a monotonic stack where popping resolves a region bounded by the nearest taller bars on each side.

4 · expert

Two pointers with running maxima

time O(n)space O(1)

Move two pointers inward from both ends, keeping leftMax and rightMax. At each step handle the side whose bar is lower: its water level is its own side's running maximum, because the other side has a wall at least as tall.

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

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

def trap(height):
    l, r = 0, len(height) - 1
    left_max = right_max = water = 0
    while l < r:
        if height[l] < height[r]:
            left_max = max(left_max, height[l])
            water += left_max - height[l]
            l += 1
        else:
            right_max = max(right_max, height[r])
            water += right_max - height[r]
            r -= 1
    return water

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

Flaws & bottlenecks

The correctness argument (why the lower side can be settled) is subtle.
Ties go to the right side; getting the comparison direction wrong gives wrong answers.
It computes only the total, not the depth at each bar (unless recorded).

Interviewer cross-questions

Why can you finish the lower side without knowing the true maximum on the other side?

Say: If height[l] < height[r], some bar on the right (r itself) is taller than bar l, so the right wall is never the limiting side for l. The level above l is then set by leftMax alone, and leftMax − height[l] is exact.

What happens when the two heights are equal?

Say: The else branch handles the right bar. Either choice is correct because both walls are at least that tall.

Which approach would you use in production?

Say: Two pointers: linear time and constant memory with no allocation. The stack version is useful when you also want the pools themselves.

Synchronized code walkthrough

Showing: Scan both sides for every bar — shares the player above; click any step to jump.

int trap(vector<int>& height) {
    int water = 0;
    int n = height.size();
    for (int i = 0; i < n; i++) {
        int leftMax = 0, rightMax = 0;
        for (int j = 0; j <= i; j++) leftMax = max(leftMax, height[j]);
        for (int j = i; j < n; j++) rightMax = max(rightMax, height[j]);
        water += min(leftMax, rightMax) - height[i];
    }
    return water;
}

public int trap(int[] height) {
    int water = 0;
    int n = height.length;
    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;
}

def trap(height):
    water = 0
    n = len(height)
    for i in range(n):
        left_max = right_max = 0
        for j in range(i + 1): left_max = max(left_max, height[j])
        for j in range(i, n): right_max = max(right_max, height[j])
        water += min(left_max, right_max) - height[i]
    return water

function trap(height: number[]): number {
  let water = 0;
  for (let i = 0; i < height.length; i++) {
    let leftMax = 0, rightMax = 0;
    for (let j = 0; j <= i; j++) leftMax = Math.max(leftMax, height[j]);
    for (let j = i; j < height.length; j++) rightMax = Math.max(rightMax, height[j]);
    water += Math.min(leftMax, rightMax) - height[i];
  }
  return water;
}

int trap(vector<int>& height) {
    int n = height.size();
    if (n == 0) return 0;
    vector<int> left(n), right(n);
    left[0] = height[0];
    for (int i = 1; i < n; i++) left[i] = max(left[i - 1], height[i]);
    right[n - 1] = height[n - 1];
    for (int i = n - 2; i >= 0; i--) right[i] = max(right[i + 1], height[i]);
    int water = 0;
    for (int i = 0; i < n; i++) water += min(left[i], right[i]) - height[i];
    return water;
}

public int trap(int[] height) {
    int n = height.length;
    if (n == 0) return 0;
    int[] left = new int[n], right = new int[n];
    left[0] = height[0];
    for (int i = 1; i < n; i++) left[i] = Math.max(left[i - 1], height[i]);
    right[n - 1] = height[n - 1];
    for (int i = n - 2; i >= 0; i--) right[i] = Math.max(right[i + 1], height[i]);
    int water = 0;
    for (int i = 0; i < n; i++) water += Math.min(left[i], right[i]) - height[i];
    return water;
}

def trap(height):
    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])
    water = 0
    for i in range(n): water += min(left[i], right[i]) - height[i]
    return water

function trap(height: number[]): number {
  const n = height.length;
  if (n === 0) return 0;
  const left = new Array<number>(n), right = new Array<number>(n);
  left[0] = height[0];
  for (let i = 1; i < n; i++) left[i] = Math.max(left[i - 1], height[i]);
  right[n - 1] = height[n - 1];
  for (let i = n - 2; i >= 0; i--) right[i] = Math.max(right[i + 1], height[i]);
  let water = 0;
  for (let i = 0; i < n; i++) water += Math.min(left[i], right[i]) - height[i];
  return water;
}

int trap(vector<int>& height) {
    vector<int> stack;
    int water = 0;
    for (int i = 0; i < (int)height.size(); i++) {
        while (!stack.empty() && height[i] > height[stack.back()]) {
            int bottom = stack.back(); stack.pop_back();
            if (stack.empty()) break;
            int left = stack.back();
            int width = i - left - 1;
            int bounded = min(height[left], height[i]) - height[bottom];
            water += width * bounded;
        }
        stack.push_back(i);
    }
    return water;
}

public int trap(int[] height) {
    Deque<Integer> stack = new ArrayDeque<>();
    int water = 0;
    for (int i = 0; i < height.length; i++) {
        while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
            int bottom = stack.pop();
            if (stack.isEmpty()) break;
            int left = stack.peek();
            int width = i - left - 1;
            int bounded = Math.min(height[left], height[i]) - height[bottom];
            water += width * bounded;
        }
        stack.push(i);
    }
    return water;
}

def trap(height):
    stack = []
    water = 0
    for i in range(len(height)):
        while stack and height[i] > height[stack[-1]]:
            bottom = stack.pop()
            if not stack: break
            left = stack[-1]
            width = i - left - 1
            bounded = min(height[left], height[i]) - height[bottom]
            water += width * bounded
        stack.append(i)
    return water

function trap(height: number[]): number {
  const stack: number[] = [];
  let water = 0;
  for (let i = 0; i < height.length; i++) {
    while (stack.length > 0 && height[i] > height[stack[stack.length - 1]]) {
      const bottom = stack.pop()!;
      if (stack.length === 0) break;
      const left = stack[stack.length - 1];
      const width = i - left - 1;
      const bounded = Math.min(height[left], height[i]) - height[bottom];
      water += width * bounded;
    }
    stack.push(i);
  }
  return water;
}

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

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

def trap(height):
    l, r = 0, len(height) - 1
    left_max = right_max = water = 0
    while l < r:
        if height[l] < height[r]:
            left_max = max(left_max, height[l])
            water += left_max - height[l]
            l += 1
        else:
            right_max = max(right_max, height[r])
            water += right_max - height[r]
            r -= 1
    return water

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