HardTwo pointers

Trapping Rain Water

Q: Why does trap give the wrong total when the heights come from a string?

Values from split are strings, and < compares strings character by character, so '10' < '9' is true. The two-pointer version then steps the wrong side: trap(['10', '0', '9']) logs 10, while the correct answer is 9. The arithmetic coerces the strings and hides the problem. Convert first with '10 0 9'.split(' ').map(Number), which gives 9.

Q: Can I get the water above each bar instead of only the total?

Yes, the prefix-max version already has everything: swap the final reduce for height.map((h, i) => Math.min(leftMax[i], rightMax[i]) - h). For [5, 2, 1, 4, 0, 3] Node logs [ 0, 2, 3, 0, 3, 0 ], which sums to the 8 from the example. The two-pointer loop visits bars out of order, so it is a poor fit for this.

Q: Is there a solution that uses a stack?

Yes, and a plain array works as the stack with push, pop and stack.at(-1) to peek. Keep indexes of bars in decreasing height. When a taller bar arrives, pop the top as the floor of a pool; the new top is the left wall and the current index the right wall, and the pool adds (Math.min(height[wall], height[i]) - height[floor]) * (i - wall - 1). It fills water in horizontal layers, gives 7 and 8 for the two examples, and takes O(n) time with O(n) space for the stack.

You get an array height of non-negative integers. Each value is a bar one unit wide, and the bars stand side by side in array order. Rain fills every dip that has a taller bar on both sides; anything that would rise above the lower of those two walls runs off. Return the total number of water units left standing.

The water above bar i is the smaller of the tallest bar at or before i and the tallest bar at or after i, minus height[i]. Both ranges include bar i itself, so a bar never holds a negative amount. The answer is that value summed over every bar. An empty array, a single bar, or a row with no dip at all holds 0; equal walls on both sides count as walls.

Examples

Input

height = [3, 0, 2, 0, 4]

Output7WhyThe walls 3 and 4 set the level at 3, so the three middle bars hold 3 + 1 + 3 = 7.

Input

height = [5, 2, 1, 4, 0, 3]

Output8WhyThe 2 and 1 sit under a level of 4 and hold 2 + 3; the 0 sits under a level of 3 and holds 3.

Constraints

Size: 0 ≤ height.length ≤ 1,500
Values: 0 ≤ height[i] ≤ 10,000
Answer: Water spills off both ends of the array; only bars with a taller bar on each side hold any.
Time limit: 10 s per run, all cases

Run your code 2 more times to open the solutions. The idea sticks better after an attempt.

3 reference approaches in Python, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: scan both sides of every bar

O(n²) time · O(1) space

Apply the rule directly. For each bar, scan from the start to find the tallest bar up to it, scan to the end to find the tallest bar from it onwards, and add the smaller of the two minus the bar's own height. Including the bar in both scans keeps every term at zero or above.

def trap(height: list[int]) -> int:
    water = 0
    for i in range(len(height)):
        left = 0
        for j in range(i + 1):  # tallest bar from the start up to i
            left = max(left, height[j])
        right = 0
        for j in range(i, len(height)):  # tallest bar from i to the end
            right = max(right, height[j])
        water += min(left, right) - height[i]
    return water

2 · Prefix and suffix maxima

O(n) time · O(n) space

The brute force keeps recomputing the same maxima. Compute them once instead: a list of the tallest bar seen so far walking left to right, and another walking right to left. itertools.accumulate(height, max) builds the running maximum in one line; running it over the reversed list and flipping the result gives the right-hand side. Then one more pass sums the water.

from itertools import accumulate


def trap(height: list[int]) -> int:
    left_max = list(accumulate(height, max))  # tallest bar up to each i
    right_max = list(accumulate(reversed(height), max))[::-1]  # tallest from each i on
    return sum(min(l, r) - h for l, r, h in zip(left_max, right_max, height))

3 · Two pointers from both ends

O(n) time · O(1) space

recommended

You don't need both maxima for every bar, only the smaller one. Start a pointer at each end and keep the tallest bar each pointer has passed. Whichever side is lower is the side whose wall is the limit, so settle the bar there: raise that side's maximum if needed, add max - height, and step that pointer inward. The pointers meet after one pass.

def trap(height: list[int]) -> int:
    left, right = 0, len(height) - 1
    left_max = right_max = 0
    water = 0
    while left < right:
        if height[left] < height[right]:
            left_max = max(left_max, height[left])
            water += left_max - height[left]
            left += 1
        else:
            right_max = max(right_max, height[right])
            water += right_max - height[right]
            right -= 1
    return water

3 reference approaches in JavaScript, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: scan both sides of every bar

O(n²) time · O(1) space

Translate the definition straight into loops. The outer for visits each index; one inner loop runs from 0 up to that index to find the left wall, a second runs from the index to the end to find the right wall, and Math.min(left, right) - height[i] goes into the total. Starting both inner loops at the bar itself is what keeps a tall bar from contributing a negative amount.

function trap(height) {
  let water = 0;
  for (let i = 0; i < height.length; i++) {
    let left = 0;
    for (let j = 0; j <= i; j++) {
      left = Math.max(left, height[j]); // tallest bar from index 0 to i
    }
    let right = 0;
    for (let j = i; j < height.length; j++) {
      right = Math.max(right, height[j]); // tallest bar from i to the end
    }
    water += Math.min(left, right) - height[i];
  }
  return water;
}

2 · Prefix and suffix maxima

O(n) time · O(n) space

The rescans keep rediscovering the same walls, so record them once. A small helper, runningMax, maps an array to the highest value seen so far by updating a closure variable inside map. Called on height it gives every left wall; called on height.toReversed() and flipped back with reverse() it gives every right wall. A reduce then totals the water. toReversed returns a copy, so the caller's array is never touched.

function runningMax(values) {
  let top = 0;
  return values.map((h) => (top = Math.max(top, h)));
}

function trap(height) {
  const leftMax = runningMax(height); // tallest bar up to each index
  const rightMax = runningMax(height.toReversed()).reverse(); // tallest from each index on
  return height.reduce((sum, h, i) => sum + Math.min(leftMax[i], rightMax[i]) - h, 0);
}

3 · Two pointers from both ends

O(n) time · O(1) space

recommended

A bar only cares about its lower wall, and you can often know which side that is without seeing the whole array. Put left at index 0 and right at the last index, each with its own running maximum. Whenever height[left] is the smaller of the two, a wall at least that tall waits on the right, so leftMax alone decides the water over left: add it and move left one step in. Otherwise do the mirror image on the right. The loop ends when the indexes meet.

function trap(height) {
  let left = 0;
  let right = height.length - 1;
  let leftMax = 0;
  let rightMax = 0;
  let water = 0;
  while (left < right) {
    if (height[left] < height[right]) {
      leftMax = Math.max(leftMax, height[left]);
      water += leftMax - height[left]; // the right wall is at least this tall
      left++;
    } else {
      rightMax = Math.max(rightMax, height[right]);
      water += rightMax - height[right]; // the left wall is at least this tall
      right--;
    }
  }
  return water;
}

3 reference approaches in TypeScript, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: scan both sides of every bar

O(n²) time · O(1) space

Follow the definition. For every index, one inner loop finds the tallest bar from 0 through i and a second finds the tallest from i to the end; the smaller of the two minus height[i] is that bar's water. Both scans include the bar itself, so a term is never negative. Every value is a number, and the annotations are the only difference from plain JavaScript.

function trap(height: number[]): number {
  let water = 0;
  for (let i = 0; i < height.length; i++) {
    let left = 0;
    for (let j = 0; j <= i; j++) left = Math.max(left, height[j]); // tallest up to i
    let right = 0;
    for (let j = i; j < height.length; j++) right = Math.max(right, height[j]); // tallest from i on
    water += Math.min(left, right) - height[i];
  }
  return water;
}

2 · Prefix and suffix maxima

O(n) time · O(n) space

Record each wall once instead of rescanning. Two typed arrays, leftMax and rightMax, are filled by one loop counting up and one counting down, each carrying the running peak. new Array<number>(n) sizes them up front, and a final loop sums Math.min(leftMax[i], rightMax[i]) - height[i]. An empty input skips every loop and returns 0.

function trap(height: number[]): number {
  const n = height.length;
  const leftMax = new Array<number>(n); // tallest bar up to each i
  const rightMax = new Array<number>(n); // tallest bar from each i on
  let best = 0;
  for (let i = 0; i < n; i++) {
    best = Math.max(best, height[i]);
    leftMax[i] = best;
  }
  best = 0;
  for (let i = n - 1; i >= 0; i--) {
    best = Math.max(best, height[i]);
    rightMax[i] = best;
  }
  let water = 0;
  for (let i = 0; i < n; i++) water += Math.min(leftMax[i], rightMax[i]) - height[i];
  return water;
}

3 · Two pointers from both ends

O(n) time · O(1) space

recommended

Only the lower wall matters, and the lower side can be settled without seeing the middle. Start left at 0 and right at the last index, each with its own running maximum. When height[left] is the smaller bar, a wall at least that tall waits on the right, so leftMax - height[left] is final: add it and step in. Otherwise do the same from the right. One pass, five number locals.

function trap(height: number[]): number {
  let left = 0;
  let right = height.length - 1;
  let leftMax = 0;
  let rightMax = 0;
  let water = 0;
  while (left < right) {
    if (height[left] < height[right]) {
      leftMax = Math.max(leftMax, height[left]);
      water += leftMax - height[left]; // the right side has a wall at least this tall
      left++;
    } else {
      rightMax = Math.max(rightMax, height[right]);
      water += rightMax - height[right]; // the left side has a wall at least this tall
      right--;
    }
  }
  return water;
}

3 reference approaches in Java, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: scan both sides of every bar

O(n²) time · O(1) space

Translate the definition into two inner for loops. For index i, the first loop runs j from 0 through i and the second from i to height.length - 1, each folding values with Math.max. Then Math.min(left, right) - height[i] goes into the total. Arrays.stream(height, 0, i + 1).max() could replace a loop, but it returns an OptionalInt and adds stream overhead to every bar for no gain.

import java.util.*;

public class Main {
    static int trap(int[] height) {
        int water = 0;
        for (int i = 0; i < height.length; i++) {
            int left = 0;
            for (int j = 0; j <= i; j++) { // tallest bar from the start up to i
                left = Math.max(left, height[j]);
            }
            int right = 0;
            for (int j = i; j < height.length; j++) { // tallest bar from i to the end
                right = Math.max(right, height[j]);
            }
            water += Math.min(left, right) - height[i];
        }
        return water;
    }
}

2 · Prefix and suffix maxima

O(n) time · O(n) space

The nested loops recompute peaks they already found on the previous index. Cache them in two int[] of length n: leftMax[i] holds the highest value in height[0..i], filled by a loop counting up, and rightMax[i] the highest in height[i..n-1], filled by a loop counting down. A shared best variable, reset between the two loops, carries the running peak. A last loop reads both arrays at each index and sums the water.

import java.util.*;

public class Main {
    static int trap(int[] height) {
        int n = height.length;
        int[] leftMax = new int[n];  // tallest bar up to each i
        int[] rightMax = new int[n]; // tallest bar from each i on
        int best = 0;
        for (int i = 0; i < n; i++) {
            best = Math.max(best, height[i]);
            leftMax[i] = best;
        }
        best = 0;
        for (int i = n - 1; i >= 0; i--) {
            best = Math.max(best, height[i]);
            rightMax[i] = best;
        }
        int water = 0;
        for (int i = 0; i < n; i++) {
            water += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
        return water;
    }
}

3 · Two pointers from both ends

O(n) time · O(1) space

recommended

Storing both peaks for every index is wasteful when only the lower one is ever used. Replace the arrays with plain int locals: left and right start at the two ends, leftMax and rightMax at 0. Each pass through the while compares the two current bars. The shorter one is bounded by its own side's peak, so update that peak with Math.max, add the difference to water, and advance that index toward the centre.

import java.util.*;

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

3 reference approaches in Go, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: scan both sides of every bar

O(n²) time · O(1) space

Go's slice expressions make the definition almost a one-liner per side. height[:i+1] is everything from the front through bar i, and height[i:] is bar i through the back; slices.Max (Go 1.21+) returns the peak of each. The built-in min picks the lower peak, and the loop adds that minus h. Because bar i sits in both subslices, neither is ever empty.

package main

import "slices"

func trap(height []int) int {
	water := 0
	for i, h := range height {
		left := slices.Max(height[:i+1]) // tallest bar from the start up to i
		right := slices.Max(height[i:])  // tallest bar from i to the end
		water += min(left, right) - h
	}
	return water
}

2 · Prefix and suffix maxima

O(n) time · O(n) space

The brute force asks for the peak of nearly the same subslice over and over. Store the answers instead. make([]int, n) gives two zeroed slices of the right length; leftMax is filled by a range loop going forward, and rightMax by a classic three-clause for counting down from n - 1, both carrying best = max(best, ...). A third loop reads the two slices side by side and totals the water.

package main

func trap(height []int) int {
	n := len(height)
	leftMax := make([]int, n)  // tallest bar up to each i
	rightMax := make([]int, n) // tallest bar from each i on
	best := 0
	for i, h := range height {
		best = max(best, h)
		leftMax[i] = best
	}
	best = 0
	for i := n - 1; i >= 0; i-- {
		best = max(best, height[i])
		rightMax[i] = best
	}
	water := 0
	for i, h := range height {
		water += min(leftMax[i], rightMax[i]) - h
	}
	return water
}

3 · Two pointers from both ends

O(n) time · O(1) space

recommended

The two slices are overkill: each bar only ever uses the smaller of its two peaks. Go's parallel assignment sets up left, right := 0, len(height)-1 and two zeroed peaks. In each iteration the shorter of height[left] and height[right] is the bar to settle, because its own side's peak is guaranteed to be the limiting wall. Update that peak, add the gap between peak and bar, and move that index one step toward the middle.

package main

func trap(height []int) int {
	left, right := 0, len(height)-1
	leftMax, rightMax := 0, 0
	water := 0
	for left < right {
		if height[left] < height[right] {
			leftMax = max(leftMax, height[left])
			water += leftMax - height[left]
			left++
		} else {
			rightMax = max(rightMax, height[right])
			water += rightMax - height[right]
			right--
		}
	}
	return water
}

3 reference approaches in C#, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: scan both sides of every bar

O(n²) time · O(1) space

Spell the definition out with two inner for loops. For index i, one loop walks j from 0 through i and the other from i to height.Length - 1, each folding the values with Math.Max; then Math.Min(left, right) - height[i] joins the total. height.Take(i + 1).Max() would replace a loop, but LINQ allocates an enumerator per bar and throws on an empty sequence, so the plain loops are both faster and safer here.

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    public static int Trap(int[] height)
    {
        int water = 0;
        for (int i = 0; i < height.Length; i++)
        {
            int left = 0;
            for (int j = 0; j <= i; j++) // tallest bar from the start up to i
            {
                left = Math.Max(left, height[j]);
            }
            int right = 0;
            for (int j = i; j < height.Length; j++) // tallest bar from i to the end
            {
                right = Math.Max(right, height[j]);
            }
            water += Math.Min(left, right) - height[i];
        }
        return water;
    }
}

2 · Prefix and suffix maxima

O(n) time · O(n) space

The nested loops rediscover peaks the previous index already found. Record them once in two int[] of length n: leftMax[i] is the tallest value in height[0..i], filled counting up, and rightMax[i] the tallest in height[i..n-1], filled counting down. One best local, reset to 0 between the two loops, carries the running peak. A final loop reads both arrays and sums the water; with n == 0 every loop body is skipped and the method returns 0 without a special case.

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    public static int Trap(int[] height)
    {
        int n = height.Length;
        int[] leftMax = new int[n];  // tallest bar up to each i
        int[] rightMax = new int[n]; // tallest bar from each i on
        int best = 0;
        for (int i = 0; i < n; i++)
        {
            best = Math.Max(best, height[i]);
            leftMax[i] = best;
        }
        best = 0;
        for (int i = n - 1; i >= 0; i--)
        {
            best = Math.Max(best, height[i]);
            rightMax[i] = best;
        }
        int water = 0;
        for (int i = 0; i < n; i++)
        {
            water += Math.Min(leftMax[i], rightMax[i]) - height[i];
        }
        return water;
    }
}

3 · Two pointers from both ends

O(n) time · O(1) space

recommended

Only the lower of the two peaks is ever used, so storing both for every index is wasted space. Keep four int locals instead: left and right start at the two ends, leftMax and rightMax at 0. Each turn of the while compares the two current bars; the shorter one is capped by its own side's peak, so raise that peak with Math.Max, add the gap to water, and move that index inward. For an empty array right starts at -1, the loop never runs, and the result is 0.

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    public static int Trap(int[] height)
    {
        int left = 0;
        int right = height.Length - 1;
        int leftMax = 0;
        int rightMax = 0;
        int water = 0;
        while (left < right)
        {
            if (height[left] < height[right])
            {
                leftMax = Math.Max(leftMax, height[left]);
                water += leftMax - height[left];
                left++;
            }
            else
            {
                rightMax = Math.Max(rightMax, height[right]);
                water += rightMax - height[right];
                right--;
            }
        }
        return water;
    }
}

3 reference approaches in C++, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: scan both sides of every bar

O(n²) time · O(1) space

Apply the rule bar by bar. For index i, one loop folds height[0..i] with max to find the left wall and another folds height[i..n-1] for the right wall; min(left, right) - height[i] goes into the total. The vector is taken by reference, so no copy is made, and both scans include the bar itself so no term is negative.

#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
public:
    int trap(vector<int>& height) {
        int n = (int)height.size();
        int water = 0;
        for (int i = 0; i < n; i++) {
            int left = 0, right = 0;
            for (int j = 0; j <= i; j++) left = max(left, height[j]);  // tallest up to i
            for (int j = i; j < n; j++) right = max(right, height[j]); // tallest from i on
            water += min(left, right) - height[i];
        }
        return water;
    }
};

2 · Prefix and suffix maxima

O(n) time · O(n) space

Compute every wall once. Two vector<int> of size n hold the running peak from the left and from the right; a forward loop fills leftMax, a backward loop fills rightMax, and a last loop adds min(leftMax[i], rightMax[i]) - height[i]. An empty input returns 0 before any indexing.

#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
public:
    int trap(vector<int>& height) {
        int n = (int)height.size();
        if (n == 0) return 0;
        vector<int> leftMax(n), rightMax(n);
        leftMax[0] = height[0];
        for (int i = 1; i < n; i++) leftMax[i] = max(leftMax[i - 1], height[i]);
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) rightMax[i] = max(rightMax[i + 1], height[i]);
        int water = 0;
        for (int i = 0; i < n; i++) water += min(leftMax[i], rightMax[i]) - height[i];
        return water;
    }
};

3 · Two pointers from both ends

O(n) time · O(1) space

recommended

Keep only two indexes and two running peaks. left starts at 0 and right at the last index. Whichever current bar is lower is capped by its own side's peak, because the other side already holds a wall at least that tall: update that peak, add the difference, and step that index inward. The indexes meet after one pass, with O(1) extra memory.

#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

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

3 reference approaches in C, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: scan both sides of every bar

O(n²) time · O(1) space

Apply the rule to every bar. For index i, one loop finds the tallest bar from 0 through i and another the tallest from i to heightSize - 1; the smaller minus height[i] is added to the total. C has no max in the standard library, so two small static helpers stand in. No memory is allocated.

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

static int max_int(int a, int b) { return a > b ? a : b; }
static int min_int(int a, int b) { return a < b ? a : b; }

int trap(int* height, int heightSize) {
    int water = 0;
    for (int i = 0; i < heightSize; i++) {
        int left = 0, right = 0;
        for (int j = 0; j <= i; j++) left = max_int(left, height[j]);           /* tallest up to i */
        for (int j = i; j < heightSize; j++) right = max_int(right, height[j]); /* tallest from i on */
        water += min_int(left, right) - height[i];
    }
    return water;
}

2 · Prefix and suffix maxima

O(n) time · O(n) space

Store each wall once. Return 0 early when heightSize is 0, then malloc two int arrays: a forward loop fills leftMax with the running peak, a backward loop fills rightMax, and a third loop sums the water. Both arrays are freed before returning, since only the int total leaves the function.

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

static int max_int(int a, int b) { return a > b ? a : b; }
static int min_int(int a, int b) { return a < b ? a : b; }

int trap(int* height, int heightSize) {
    if (heightSize == 0) return 0;
    int* leftMax = malloc(heightSize * sizeof *leftMax);   /* tallest bar up to each i */
    int* rightMax = malloc(heightSize * sizeof *rightMax); /* tallest bar from each i on */
    leftMax[0] = height[0];
    for (int i = 1; i < heightSize; i++) leftMax[i] = max_int(leftMax[i - 1], height[i]);
    rightMax[heightSize - 1] = height[heightSize - 1];
    for (int i = heightSize - 2; i >= 0; i--) rightMax[i] = max_int(rightMax[i + 1], height[i]);
    int water = 0;
    for (int i = 0; i < heightSize; i++) water += min_int(leftMax[i], rightMax[i]) - height[i];
    free(leftMax);
    free(rightMax);
    return water;
}

3 · Two pointers from both ends

O(n) time · O(1) space

recommended

Drop the arrays and keep two indexes with two running peaks. left starts at 0 and right at heightSize - 1; the lower of the two current bars is capped by its own side's peak, because the other side already has a wall at least that tall. Raise that peak, add the difference and step inward. An empty array gives right = -1, so the loop never runs and nothing is read.

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

int trap(int* height, int heightSize) {
    int left = 0, right = heightSize - 1;
    int leftMax = 0, rightMax = 0, water = 0;
    while (left < right) {
        if (height[left] < height[right]) {
            if (height[left] > leftMax) leftMax = height[left];
            water += leftMax - height[left];
            left++;
        } else {
            if (height[right] > rightMax) rightMax = height[right];
            water += rightMax - height[right];
            right--;
        }
    }
    return water;
}

3 reference approaches in Kotlin, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: scan both sides of every bar

O(n²) time · O(1) space

Apply the rule bar by bar. For index i, (0..i).maxOf { height[it] } finds the tallest bar up to it and (i until height.size).maxOf { … } the tallest from it onwards; minOf(left, right) - height[i] is the water there. Both ranges contain i, so neither is empty and no term goes below zero.

class Solution {
    fun trap(height: IntArray): Int {
        var water = 0
        for (i in height.indices) {
            val left = (0..i).maxOf { height[it] } // tallest bar from the start up to i
            val right = (i until height.size).maxOf { height[it] } // tallest bar from i to the end
            water += minOf(left, right) - height[i]
        }
        return water
    }
}

2 · Prefix and suffix maxima

O(n) time · O(n) space

Compute every maximum once. height.runningReduce { a, b -> maxOf(a, b) } gives the tallest bar seen so far from the left; running it over height.reversedArray() and viewing the result with asReversed() gives the tallest bar from each index to the end. One sumOf over the indices adds up the water.

class Solution {
    fun trap(height: IntArray): Int {
        val leftMax = height.runningReduce { a, b -> maxOf(a, b) } // tallest bar up to each i
        val rightMax = height.reversedArray().runningReduce { a, b -> maxOf(a, b) }.asReversed() // from each i on
        return height.indices.sumOf { minOf(leftMax[it], rightMax[it]) - height[it] }
    }
}

3 · Two pointers from both ends

O(n) time · O(1) space

recommended

Only the lower of the two maxima matters, so keep a var index at each end with the tallest bar it has passed. The side whose current bar is shorter is capped by its own maximum: raise that maximum with maxOf, add the difference, and step inward. The while loop ends when the indices meet, in O(1) extra space.

class Solution {
    fun trap(height: IntArray): Int {
        var left = 0
        var right = height.size - 1
        var leftMax = 0
        var rightMax = 0
        var water = 0
        while (left < right) {
            if (height[left] < height[right]) {
                leftMax = maxOf(leftMax, height[left])
                water += leftMax - height[left]
                left++
            } else {
                rightMax = maxOf(rightMax, height[right])
                water += rightMax - height[right]
                right--
            }
        }
        return water
    }
}

3 reference approaches in Rust, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: scan both sides of every bar

O(n²) time · O(1) space

Apply the rule bar by bar with slices. height[..=i].iter().max() is the tallest bar up to i and height[i..].iter().max() the tallest from it onwards. Both slices contain bar i, so the Option<&i32> is always Some and unwrap cannot panic.

impl Solution {
    pub fn trap(height: Vec<i32>) -> i32 {
        let mut water = 0;
        for i in 0..height.len() {
            let left = *height[..=i].iter().max().unwrap(); // tallest bar from the start up to i
            let right = *height[i..].iter().max().unwrap(); // tallest bar from i to the end
            water += left.min(right) - height[i];
        }
        water
    }
}

2 · Prefix and suffix maxima

O(n) time · O(n) space

Compute every maximum once with the scan iterator adapter, which carries a running state: forwards it collects the tallest bar so far into a Vec<i32>, and over iter().rev() it collects the tallest bar from the right, reversed back into place. A zip of the three sequences and sum add up the water.

impl Solution {
    pub fn trap(height: Vec<i32>) -> i32 {
        let running_max = |best: &mut i32, &h: &i32| {
            *best = (*best).max(h);
            Some(*best)
        };
        let left_max: Vec<i32> = height.iter().scan(0, running_max).collect(); // tallest bar up to each i
        let mut right_max: Vec<i32> = height.iter().rev().scan(0, running_max).collect();
        right_max.reverse(); // tallest bar from each i on
        height
            .iter()
            .zip(left_max.iter().zip(&right_max))
            .map(|(&h, (&l, &r))| l.min(r) - h)
            .sum()
    }
}

3 · Two pointers from both ends

O(n) time · O(1) space

recommended

Keep a usize index at each end and the tallest bar each has passed. The side whose bar is shorter is capped by its own maximum, so settle it and step inward. The right index starts at height.len().saturating_sub(1), so an empty vector does not underflow.

impl Solution {
    pub fn trap(height: Vec<i32>) -> i32 {
        let (mut left, mut right) = (0, height.len().saturating_sub(1));
        let (mut left_max, mut right_max) = (0, 0);
        let mut water = 0;
        while left < right {
            if height[left] < height[right] {
                left_max = left_max.max(height[left]);
                water += left_max - height[left];
                left += 1;
            } else {
                right_max = right_max.max(height[right]);
                water += right_max - height[right];
                right -= 1;
            }
        }
        water
    }
}

3 reference approaches in Swift, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: scan both sides of every bar

O(n²) time · O(1) space

Apply the rule bar by bar with array slices. height[...i].max() is the tallest bar up to i and height[i...].max() the tallest from it onwards. max() returns an optional, and the force unwrap is safe because both slices contain bar i.

class Solution {
    func trap(_ height: [Int]) -> Int {
        var water = 0
        for i in height.indices {
            let left = height[...i].max()! // tallest bar from the start up to i
            let right = height[i...].max()! // tallest bar from i to the end
            water += min(left, right) - height[i]
        }
        return water
    }
}

2 · Prefix and suffix maxima

O(n) time · O(n) space

Compute every maximum once. A map whose closure updates a captured best builds the tallest bar so far from the left; the same over height.reversed(), wrapped in Array(… .reversed()), gives the tallest bar from each index to the end. A reduce over height.indices sums the water.

class Solution {
    func trap(_ height: [Int]) -> Int {
        var best = 0
        let leftMax = height.map { h -> Int in best = max(best, h); return best } // tallest bar up to each i
        best = 0
        let rightMax = Array(height.reversed().map { h -> Int in best = max(best, h); return best }.reversed())
        return height.indices.reduce(0) { $0 + min(leftMax[$1], rightMax[$1]) - height[$1] }
    }
}

3 · Two pointers from both ends

O(n) time · O(1) space

recommended

Keep an index at each end and the tallest bar each has passed. The side whose bar is shorter is capped by its own maximum, so settle it and step inward. For an empty array right starts at -1, and the while condition is false from the start, so nothing traps.

class Solution {
    func trap(_ height: [Int]) -> Int {
        var left = 0, right = height.count - 1
        var leftMax = 0, rightMax = 0
        var water = 0
        while left < right {
            if height[left] < height[right] {
                leftMax = max(leftMax, height[left])
                water += leftMax - height[left]
                left += 1
            } else {
                rightMax = max(rightMax, height[right])
                water += rightMax - height[right]
                right -= 1
            }
        }
        return water
    }
}

3 reference approaches in PHP, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: scan both sides of every bar

O(n²) time · O(1) space

Apply the rule bar by bar. max(array_slice($height, 0, $i + 1)) is the tallest bar up to $i and max(array_slice($height, $i)) the tallest from it onwards; the smaller of the two minus $height[$i] is the water there. Both slices contain bar $i, so max never sees an empty array.

<?php

class Solution {
    /**
     * @param int[] $height
     * @return int
     */
    function trap(array $height): int {
        $water = 0;
        foreach ($height as $i => $h) {
            $left = max(array_slice($height, 0, $i + 1)); // tallest bar from the start up to $i
            $right = max(array_slice($height, $i)); // tallest bar from $i to the end
            $water += min($left, $right) - $h;
        }
        return $water;
    }
}

2 · Prefix and suffix maxima

O(n) time · O(n) space

Compute every maximum once into two arrays pre-filled with array_fill(0, $n, 0): $leftMax counting up and $rightMax counting down, each carrying a running $best. A last foreach adds the smaller of the two maxima minus the bar.

<?php

class Solution {
    /**
     * @param int[] $height
     * @return int
     */
    function trap(array $height): int {
        $n = count($height);
        $leftMax = array_fill(0, $n, 0); // tallest bar up to each $i
        $rightMax = array_fill(0, $n, 0); // tallest bar from each $i on
        $best = 0;
        for ($i = 0; $i < $n; $i++) {
            $best = max($best, $height[$i]);
            $leftMax[$i] = $best;
        }
        $best = 0;
        for ($i = $n - 1; $i >= 0; $i--) {
            $best = max($best, $height[$i]);
            $rightMax[$i] = $best;
        }
        $water = 0;
        foreach ($height as $i => $h) {
            $water += min($leftMax[$i], $rightMax[$i]) - $h;
        }
        return $water;
    }
}

3 · Two pointers from both ends

O(n) time · O(1) space

recommended

Keep an index at each end and the tallest bar each has passed. The side whose bar is shorter is capped by its own maximum, so settle it and step inward. For an empty array $right starts at -1 and the while never runs.

<?php

class Solution {
    /**
     * @param int[] $height
     * @return int
     */
    function trap(array $height): int {
        $left = 0;
        $right = count($height) - 1;
        $leftMax = 0;
        $rightMax = 0;
        $water = 0;
        while ($left < $right) {
            if ($height[$left] < $height[$right]) {
                $leftMax = max($leftMax, $height[$left]);
                $water += $leftMax - $height[$left];
                $left++;
            } else {
                $rightMax = max($rightMax, $height[$right]);
                $water += $rightMax - $height[$right];
                $right--;
            }
        }
        return $water;
    }
}

3 reference approaches in Ruby, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: scan both sides of every bar

O(n²) time · O(1) space

Apply the rule bar by bar. height[0..i].max is the tallest bar up to i and height[i..].max (an endless range) the tallest from it onwards; the smaller of the two minus height[i] is the water there. each_index.sum adds the terms up.

# @param {Integer[]} height
# @return {Integer}
def trap(height)
  height.each_index.sum do |i|
    left = height[0..i].max # tallest bar from the start up to i
    right = height[i..].max # tallest bar from i to the end
    [left, right].min - height[i]
  end
end

2 · Prefix and suffix maxima

O(n) time · O(n) space

Compute every maximum once. A map whose block updates a running best builds the tallest bar so far from the left; the same over reverse_each, reversed back, gives the tallest from each index to the end. zip lines the three arrays up and sum adds the water.

# @param {Integer[]} height
# @return {Integer}
def trap(height)
  best = 0
  left_max = height.map { |h| best = [best, h].max } # tallest bar up to each i
  best = 0
  right_max = height.reverse_each.map { |h| best = [best, h].max }.reverse # tallest from each i on
  height.zip(left_max, right_max).sum { |h, l, r| [l, r].min - h }
end

3 · Two pointers from both ends

O(n) time · O(1) space

recommended

# @param {Integer[]} height
# @return {Integer}
def trap(height)
  left = 0
  right = height.length - 1
  left_max = right_max = 0
  water = 0
  while left < right
    if height[left] < height[right]
      left_max = [left_max, height[left]].max
      water += left_max - height[left]
      left += 1
    else
      right_max = [right_max, height[right]].max
      water += right_max - height[right]
      right -= 1
    end
  end
  water
end

3 reference approaches in Dart, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: scan both sides of every bar

O(n²) time · O(1) space

Apply the rule bar by bar. height.getRange(0, i + 1).reduce(max) is the tallest bar up to i and height.getRange(i, height.length).reduce(max) the tallest from it onwards, with max and min from dart:math. Both ranges contain bar i, so reduce never sees an empty iterable.

import 'dart:math';

class Solution {
  int trap(List<int> height) {
    var water = 0;
    for (var i = 0; i < height.length; i++) {
      final left = height.getRange(0, i + 1).reduce(max); // tallest bar from the start up to i
      final right = height.getRange(i, height.length).reduce(max); // tallest bar from i to the end
      water += min(left, right) - height[i];
    }
    return water;
  }
}

2 · Prefix and suffix maxima

O(n) time · O(n) space

Compute every maximum once into two fixed-length lists from List.filled(n, 0): leftMax counting up and rightMax counting down, each carrying a running best. A last loop adds the smaller of the two maxima minus the bar.

import 'dart:math';

class Solution {
  int trap(List<int> height) {
    final n = height.length;
    final leftMax = List.filled(n, 0); // tallest bar up to each i
    final rightMax = List.filled(n, 0); // tallest bar from each i on
    var best = 0;
    for (var i = 0; i < n; i++) {
      best = max(best, height[i]);
      leftMax[i] = best;
    }
    best = 0;
    for (var i = n - 1; i >= 0; i--) {
      best = max(best, height[i]);
      rightMax[i] = best;
    }
    var water = 0;
    for (var i = 0; i < n; i++) {
      water += min(leftMax[i], rightMax[i]) - height[i];
    }
    return water;
  }
}

3 · Two pointers from both ends

O(n) time · O(1) space

recommended

Keep an index at each end and the tallest bar each has passed. The side whose bar is shorter is capped by its own maximum, so settle it and step inward. For an empty list right starts at -1 and the while never runs.

import 'dart:math';

class Solution {
  int trap(List<int> height) {
    var left = 0, right = height.length - 1;
    var leftMax = 0, rightMax = 0;
    var water = 0;
    while (left < right) {
      if (height[left] < height[right]) {
        leftMax = max(leftMax, height[left]);
        water += leftMax - height[left];
        left++;
      } else {
        rightMax = max(rightMax, height[right]);
        water += rightMax - height[right];
        right--;
      }
    }
    return water;
  }
}

3 reference approaches in Scala, from brute force to the one to reach for. Compare them with yours.

1 · Brute force: scan both sides of every bar

O(n²) time · O(1) space

Apply the rule bar by bar. height.view.slice(0, i + 1).max is the tallest bar up to i and height.view.slice(i, height.length).max the tallest from it onwards; the view reads the array in place instead of copying a slice. Mapping every index to its water and calling sum gives the total.

object Solution {
  def trap(height: Array[Int]): Int =
    height.indices.map { i =>
      val left = height.view.slice(0, i + 1).max // tallest bar from the start up to i
      val right = height.view.slice(i, height.length).max // tallest bar from i to the end
      math.min(left, right) - height(i)
    }.sum
}

2 · Prefix and suffix maxima

O(n) time · O(n) space

Compute every maximum once with the collection scans. height.scanLeft(0)(_ max _).tail is the tallest bar so far from the left and height.scanRight(0)(_ max _).init the tallest from each index to the end; tail and init drop the seed each scan adds. One more pass over the indices sums the water.

object Solution {
  def trap(height: Array[Int]): Int = {
    val leftMax = height.scanLeft(0)(_ max _).tail // tallest bar up to each i
    val rightMax = height.scanRight(0)(_ max _).init // tallest bar from each i on
    height.indices.map(i => math.min(leftMax(i), rightMax(i)) - height(i)).sum
  }
}

3 · Two pointers from both ends

O(n) time · O(1) space

recommended

Keep a var index at each end and the tallest bar each has passed. The side whose bar is shorter is capped by its own maximum, so settle it and step inward. A while loop fits two indices that move on a condition, and it needs no early exit, so no boundary either.

object Solution {
  def trap(height: Array[Int]): Int = {
    var left = 0
    var right = height.length - 1
    var leftMax = 0
    var rightMax = 0
    var water = 0
    while (left < right) {
      if (height(left) < height(right)) {
        leftMax = math.max(leftMax, height(left))
        water += leftMax - height(left)
        left += 1
      } else {
        rightMax = math.max(rightMax, height(right))
        water += rightMax - height(right)
        right -= 1
      }
    }
    water
  }
}

FAQ for JavaScript

How can the two-pointer loop ignore the bars it has not visited yet?

Each side keeps its tallest bar so far, and the side that does not move is sitting on a bar at least as tall as anything the other side has passed. So when height[left] < height[right], the right wall for the bar at left is already guaranteed to be no lower than leftMax, and whatever lies between the indexes can only raise it. The water over that bar is therefore exactly leftMax - height[left].

Why does trap give the wrong total when the heights come from a string?

Values from split are strings, and < compares strings character by character, so '10' < '9' is true. The two-pointer version then steps the wrong side: trap(['10', '0', '9']) logs 10, while the correct answer is 9. The arithmetic coerces the strings and hides the problem. Convert first with '10 0 9'.split(' ').map(Number), which gives 9.

Can I get the water above each bar instead of only the total?

Yes, the prefix-max version already has everything: swap the final reduce for height.map((h, i) => Math.min(leftMax[i], rightMax[i]) - h). For [5, 2, 1, 4, 0, 3] Node logs [ 0, 2, 3, 0, 3, 0 ], which sums to the 8 from the example. The two-pointer loop visits bars out of order, so it is a poor fit for this.

Is there a solution that uses a stack?

Yes, and a plain array works as the stack with push, pop and stack.at(-1) to peek. Keep indexes of bars in decreasing height. When a taller bar arrives, pop the top as the floor of a pool; the new top is the left wall and the current index the right wall, and the pool adds (Math.min(height[wall], height[i]) - height[floor]) * (i - wall - 1). It fills water in horizontal layers, gives 7 and 8 for the two examples, and takes O(n) time with O(n) space for the stack.

How would I solve the 2-D version on a grid in JavaScript?

Pointers stop working because water can leave in four directions. Start from every border cell and always expand from the lowest boundary cell: a neighbour below the current level holds level - height and joins the boundary at Math.max(level, height). That needs a min-heap, and JavaScript has none built in, so write a small binary heap over an array (sorting the whole boundary after each push turns the O(m·n·log(m·n)) algorithm into something much slower).

FAQ for Java

Why does the sweep only need the peak on the side it moves?

The if picks the side whose current bar is shorter. If height[left] < height[right], the bar at right is already taller than the left one, so the right-hand boundary for index left is at least that tall; bars still unvisited in the middle could only make it taller. The limiting wall is therefore leftMax, and the answer for left is final. When the right bar is the shorter or equal one, the else branch applies the same reasoning to rightMax.

Can the total overflow an int in Java?

Yes, and Java will not warn you: int is 32 bits and wraps around on overflow. One bar adds at most Integer.MAX_VALUE, yet several bars together can pass it, and trap(new int[] {Integer.MAX_VALUE, 0, 0, Integer.MAX_VALUE}) returns -2 with an int total. Make it long water = 0 with a long return type and the same call gives 4294967294, or use Math.addExact to get an ArithmeticException instead of a wrong number. The per-bar term leftMax - height[left] itself cannot overflow, as both operands are non-negative ints.

What if the heights arrive as a List of Integer?

Copy them into an int[] first, for example list.stream().mapToInt(Integer::intValue).toArray(), and keep the method as it is. Working on the List<Integer> directly unboxes on every get call, and it invites a classic bug: < unboxes both sides and compares values, but == between two Integer objects compares references, which can fail for values outside the small cached range.

Is there a stack-based solution in Java?

Yes. Store indices in an ArrayDeque<Integer> used as a stack (push, pop, peek), which is the recommended replacement for the legacy synchronized Stack class, and keep their heights decreasing from bottom to top. A taller incoming bar pops the top index, which becomes the bottom of a pool walled by the new bar and the index left on top; that pool contributes (Math.min(leftWall, rightWall) - bottom) * width units. Water is counted in horizontal layers rather than column by column, in O(n) time with O(n) extra space, and the totals for the two examples are still 7 and 8.

How do I solve the 2-D grid version in Java?

Use a PriorityQueue<int[]> holding {height, row, col} triples, created with new PriorityQueue<>(Comparator.comparingInt(c -> c[0])) so the lowest cell comes out first, and a boolean[][] visited. Offer every border cell, then keep calling poll: the polled height is the current water level, and each unvisited neighbour below it traps level - height before being offered with Math.max(level, height). A sweep from two ends cannot work here, since water escapes in four directions. The cost is O(m·n·log(m·n)) for an m by n grid.

FAQ for Go

How can the two-index loop ignore the bars it has not visited yet?

It only settles a bar when that bar is the shorter of height[left] and height[right]. Say the left one is shorter: then the right index stands on a bar taller than it, so somewhere on the right there is already a wall at least as high as leftMax. Whatever sits in between can only raise that wall, never lower it, so leftMax alone fixes the level over height[left]. The else branch is the mirror case.

Will slices.Max panic on an empty slice?

Yes: slices.Max panics when given a slice of length zero, because there is no value it could return. The brute force never hits that, since height[:i+1] and height[i:] both contain index i, and for a nil or empty input the range loop never runs. The built-in max used in the other two versions is different: it takes separate arguments, like max(best, h), needs no import and has no slice to be empty.

Should trap take a pointer to the slice?

No. A slice value is a small header (pointer, length, capacity), so passing height copies the header and the function reads the caller's backing array directly; *[]int would only matter if trap needed to change the length the caller sees. Since every version only reads height, the plain []int parameter is the idiomatic choice, and it accepts nil as well.

Is there a stack-based solution in Go?

Yes, and Go needs no stack type for it: a []int of indices does the job, growing with append and shrinking with st = st[:len(st)-1]. Keep the heights at those indices decreasing. When a taller bar shows up, pop the top index; it is the bottom of a pool bounded by the new bar and whatever index is now on top. That pool adds (min(leftWall, rightWall) - bottom) * width units, filling the water layer by layer. It is O(n) time and O(n) extra space for the slice.

How do I trap rain water on a 2-D grid in Go?

Two indices cannot handle it, because water can leave a cell in four directions. Define a slice type of cells and give it Len, Less, Swap, Push and Pop so container/heap can use it as a min-heap by height. Seed it with every border cell, marking each in a [][]bool, then pop the lowest cell each round and treat its height as the current level: an unvisited neighbour below it adds level - height and is pushed with height max(level, height). For an m by n grid this is O(m·n·log(m·n)) time.

FAQ for C#

Why does the sweep only need the peak on the side it moves?

The if chooses the side whose current bar is shorter. When height[left] < height[right], the bar at right already stands taller than the one at left, so the right-hand wall for index left is at least that high, and any unvisited bar in between could only raise it. The limiting wall is leftMax, which makes the water over left final. When the right bar is the shorter or equal one, the else branch applies the same argument to rightMax.

Can the total overflow an int in C#?

Yes, and by default it wraps silently: C# arithmetic is unchecked unless you compile with -checked or wrap the sum in a checked { } block, which throws OverflowException instead. One bar contributes at most int.MaxValue, but several bars together can pass it: Trap(new[] { int.MaxValue, 0, 0, int.MaxValue }) returns -2 with an int total. Declare long water = 0 and return long and the same call gives 4294967294. The per-bar term leftMax - height[left] cannot overflow on its own, since both operands are non-negative ints.

What if the heights arrive as a List<int> or an IEnumerable<int>?

Call .ToArray() once and keep the method on int[]. Indexing a List<int> works but goes through the indexer property on every access, and an IEnumerable<int> cannot be indexed at all: Enumerable.ElementAt(i) walks from the start each time and turns the two-pointer sweep into O(n²). If you want to avoid the copy for an existing array, take a ReadOnlySpan<int> instead; the loops read identically and an int[] converts to it implicitly.

Is there a stack-based solution in C#?

Yes. Use a Stack<int> of indices (Push, Pop, Peek, and TryPeek when it may be empty) and keep their heights decreasing from bottom to top. When a taller bar arrives, pop the top index: it is the floor of a pool walled by the new bar and the index now on top of the stack, and the pool holds (Math.Min(leftWall, rightWall) - floor) * width units. Water is counted in horizontal layers rather than per column, in O(n) time with O(n) extra space, and the two examples still total 7 and 8.

How do I solve the 2-D grid version in C#?

Use PriorityQueue<(int row, int col), int> from .NET 6 with the cell height as the priority, so Dequeue always hands back the lowest cell, plus a bool[,] visited. Enqueue every border cell, then loop: the dequeued height is the current water level, and each unvisited neighbour below it traps level - height before being enqueued with Math.Max(level, height). A sweep from two ends cannot work on a grid, because water escapes in four directions. The cost is O(m·n·log(m·n)) for an m by n grid.

Keep going

N-Queens38 / 40 · Backtracking · Hard

trap.js

JavaScript 26.10

Not run yet

+ 7 hidden

Input

height = [3, 0, 2, 0, 4]

Expected

The walls 3 and 4 set the level at 3, so the three middle bars hold 3 + 1 + 3 = 7.