42. Trapping Rain Water - Explanation

Description

You are given an array of non-negative integers height which represent an elevation map. Each value height[i] represents the height of a bar, which has a width of 1.

Return the total amount of water that can be trapped between the bars.

Example 1:

Input: height = [0,2,0,3,1,0,1,3,2,1]

Output: 9

Constraints:

1 <= height.length <= 20,000
0 <= height[i] <= 100,000

Topics

Recommended Time & Space Complexity

You should aim for a solution as good or better than O(n) time and O(n) space, where n is the size of the input array.

Hint 1

How can we determine the amount of water that can be trapped at a specific position in the array? Perhaps looking at the image might help clarify.

Hint 2

From the image, we can see that to calculate the amount of water trapped at a position, the greater element to the left l and the greater element to the right r of the current position are crucial. The formula for the trapped water at index i is given by: min(height[l], height[r]) - height[i].

Hint 3

A brute force solution would involve iterating through the array with index i, finding the greater elements to the left (l) and right (r) for each index, and then calculating the trapped water for that position. The total amount of trapped water would be the sum of the water trapped at each index. Finding l and r for each index involves repeated work, resulting in an O(n^2) solution. Can you think of a more efficient approach? Maybe there is something that we can precompute and store in arrays.

Hint 4

We can store the prefix maximum in an array by iterating from left to right and the suffix maximum in another array by iterating from right to left. For example, in [1, 5, 2, 3, 4], for the element 3, the prefix maximum is 5, and the suffix maximum is 4. Once these arrays are built, we can iterate through the array with index i and calculate the total water trapped at each position using the formula: min(prefix[i], suffix[i]) - height[i].

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Arrays - Basic array traversal and element access
Prefix and Suffix Arrays - Precomputing running maximums from both directions
Two Pointers - Using left and right pointers that move toward each other based on conditions
Stack - Using a monotonic stack to track indices and compute bounded regions

1. Brute Force

Intuition

For each position, the water trapped above it depends on the tallest bar to its left and the tallest bar to its right.
If we know these two values, the water at index i is:

min(leftMax, rightMax) - height[i]

The brute-force method recomputes the left maximum and right maximum for every index by scanning the array each time.

Algorithm

If the input list is empty, return 0.
Let n be the length of the array and initialize res = 0.
For each index i:
- Compute leftMax by scanning from index 0 to i.
- Compute rightMax by scanning from index i + 1 to the end.
- Add min(leftMax, rightMax) - height[i] to res.
After processing all positions, return res.

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0
        n = len(height)
        res = 0

        for i in range(n):
            leftMax = rightMax = height[i]

            for j in range(i):
                leftMax = max(leftMax, height[j])
            for j in range(i + 1, n):
                rightMax = max(rightMax, height[j])

            res += min(leftMax, rightMax) - height[i]
        return res

public class Solution {
    public int trap(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        int n = height.length;
        int res = 0;

        for (int i = 0; i < n; i++) {
            int leftMax = height[i];
            int rightMax = height[i];

            for (int j = 0; j < i; j++) {
                leftMax = Math.max(leftMax, height[j]);
            }
            for (int j = i + 1; j < n; j++) {
                rightMax = Math.max(rightMax, height[j]);
            }

            res += Math.min(leftMax, rightMax) - height[i];
        }
        return res;
    }
}

class Solution {
public:
    int trap(vector<int>& height) {
        if (height.empty()) {
            return 0;
        }
        int n = height.size();
        int res = 0;

        for (int i = 0; i < n; i++) {
            int leftMax = height[i];
            int rightMax = height[i];

            for (int j = 0; j < i; j++) {
                leftMax = max(leftMax, height[j]);
            }
            for (int j = i + 1; j < n; j++) {
                rightMax = max(rightMax, height[j]);
            }

            res += min(leftMax, rightMax) - height[i];
        }
        return res;
    }
};

class Solution {
    /**
     * @param {number[]} height
     * @return {number}
     */
    trap(height) {
        if (!height.length) {
            return 0;
        }
        let n = height.length;
        let res = 0;

        for (let i = 0; i < n; i++) {
            let leftMax = height[i];
            let rightMax = height[i];

            for (let j = 0; j < i; j++) {
                leftMax = Math.max(leftMax, height[j]);
            }
            for (let j = i + 1; j < n; j++) {
                rightMax = Math.max(rightMax, height[j]);
            }

            res += Math.min(leftMax, rightMax) - height[i];
        }
        return res;
    }
}

public class Solution {
    public int Trap(int[] height) {
        if (height == null || height.Length == 0) {
            return 0;
        }
        int n = height.Length;
        int res = 0;

        for (int i = 0; i < n; i++) {
            int leftMax = height[i];
            int rightMax = height[i];

            for (int j = 0; j < i; j++) {
                leftMax = Math.Max(leftMax, height[j]);
            }
            for (int j = i + 1; j < n; j++) {
                rightMax = Math.Max(rightMax, height[j]);
            }

            res += Math.Min(leftMax, rightMax) - height[i];
        }

        return res;
    }
}

func trap(height []int) int {
    if len(height) == 0 {
        return 0
    }
    n := len(height)
    res := 0

    for i := 0; i < n; i++ {
        leftMax := height[i]
        rightMax := height[i]

        for j := 0; j < i; j++ {
            if height[j] > leftMax {
                leftMax = height[j]
            }
        }
        for j := i + 1; j < n; j++ {
            if height[j] > rightMax {
                rightMax = height[j]
            }
        }

        res += min(leftMax, rightMax) - height[i]
    }
    return res
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

class Solution {
    fun trap(height: IntArray): Int {
        if (height.isEmpty()) return 0
        val n = height.size
        var res = 0

        for (i in 0 until n) {
            var leftMax = height[i]
            var rightMax = height[i]

            for (j in 0 until i) {
                leftMax = maxOf(leftMax, height[j])
            }
            for (j in i + 1 until n) {
                rightMax = maxOf(rightMax, height[j])
            }

            res += minOf(leftMax, rightMax) - height[i]
        }
        return res
    }
}

class Solution {
    func trap(_ height: [Int]) -> Int {
        if height.isEmpty {
            return 0
        }
        let n = height.count
        var res = 0

        for i in 0..<n {
            var leftMax = height[i]
            var rightMax = height[i]

            for j in 0..<i {
                leftMax = max(leftMax, height[j])
            }
            for j in (i + 1)..<n {
                rightMax = max(rightMax, height[j])
            }

            res += min(leftMax, rightMax) - height[i]
        }
        return res
    }
}

impl Solution {
    pub fn trap(height: Vec<i32>) -> i32 {
        if height.is_empty() {
            return 0;
        }
        let n = height.len();
        let mut res = 0;

        for i in 0..n {
            let mut left_max = height[i];
            let mut right_max = height[i];

            for j in 0..i {
                left_max = left_max.max(height[j]);
            }
            for j in (i + 1)..n {
                right_max = right_max.max(height[j]);
            }

            res += left_max.min(right_max) - height[i];
        }
        res
    }
}

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(1)$

2. Prefix & Suffix Arrays

Intuition

Instead of recomputing the tallest bar to the left and right for every index, we can precompute these values once.
We build two arrays:

leftMax[i] = tallest bar from the start up to index i
rightMax[i] = tallest bar from the end up to index i

Once we have these, the trapped water at position i is simply:

min(leftMax[i], rightMax[i]) - height[i]

This removes the repeated work from the brute-force approach and makes the solution more efficient and easier to understand.

Algorithm

If the array is empty, return 0.
Create two arrays:
- leftMax of size n
- rightMax of size n
Fill leftMax:
- leftMax[0] = height[0]
- For each i from 1 to n - 1,
  leftMax[i] = max(leftMax[i - 1], height[i])
Fill rightMax:
- rightMax[n - 1] = height[n - 1]
- For each i from n - 2 down to 0,
  rightMax[i] = max(rightMax[i + 1], height[i])
Compute trapped water:
- For each index i, add min(leftMax[i], rightMax[i]) - height[i] to the result.
Return the total trapped water.

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        if n == 0:
            return 0

        leftMax = [0] * n
        rightMax = [0] * n

        leftMax[0] = height[0]
        for i in range(1, n):
            leftMax[i] = max(leftMax[i - 1], height[i])

        rightMax[n - 1] = height[n - 1]
        for i in range(n - 2, -1, -1):
            rightMax[i] = max(rightMax[i + 1], height[i])

        res = 0
        for i in range(n):
            res += min(leftMax[i], rightMax[i]) - height[i]
        return res

public class Solution {
    public int trap(int[] height) {
        int n = height.length;
        if (n == 0) {
            return 0;
        }

        int[] leftMax = new int[n];
        int[] 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]);
        }

        int res = 0;
        for (int i = 0; i < n; i++) {
            res += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
        return res;
    }
}

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        if (n == 0) {
            return 0;
        }

        vector<int> leftMax(n);
        vector<int> 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 res = 0;
        for (int i = 0; i < n; i++) {
            res += min(leftMax[i], rightMax[i]) - height[i];
        }
        return res;
    }
};

class Solution {
    /**
     * @param {number[]} height
     * @return {number}
     */
    trap(height) {
        let n = height.length;
        if (n === 0) {
            return 0;
        }

        let leftMax = new Array(n).fill(0);
        let rightMax = new Array(n).fill(0);

        leftMax[0] = height[0];
        for (let i = 1; i < n; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }

        rightMax[n - 1] = height[n - 1];
        for (let i = n - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }

        let res = 0;
        for (let i = 0; i < n; i++) {
            res += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
        return res;
    }
}

public class Solution {
    public int Trap(int[] height) {
        int n = height.Length;
        if (n == 0) {
            return 0;
        }

        int[] leftMax = new int[n];
        int[] 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]);
        }

        int res = 0;
        for (int i = 0; i < n; i++) {
            res += Math.Min(leftMax[i], rightMax[i]) - height[i];
        }
        return res;
    }
}

func trap(height []int) int {
    n := len(height)
    if n == 0 {
        return 0
    }

    leftMax := make([]int, n)
    rightMax := make([]int, n)

    leftMax[0] = height[0]
    for i := 1; i < n; i++ {
        leftMax[i] = max(leftMax[i-1], height[i])
    }

    rightMax[n-1] = height[n-1]
    for i := n - 2; i >= 0; i-- {
        rightMax[i] = max(rightMax[i+1], height[i])
    }

    res := 0
    for i := 0; i < n; i++ {
        res += min(leftMax[i], rightMax[i]) - height[i]
    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

class Solution {
    fun trap(height: IntArray): Int {
        val n = height.size
        if (n == 0) return 0

        val leftMax = IntArray(n)
        val rightMax = IntArray(n)

        leftMax[0] = height[0]
        for (i in 1 until n) {
            leftMax[i] = maxOf(leftMax[i - 1], height[i])
        }

        rightMax[n - 1] = height[n - 1]
        for (i in n - 2 downTo 0) {
            rightMax[i] = maxOf(rightMax[i + 1], height[i])
        }

        var res = 0
        for (i in 0 until n) {
            res += minOf(leftMax[i], rightMax[i]) - height[i]
        }
        return res
    }
}

class Solution {
    func trap(_ height: [Int]) -> Int {
        let n = height.count
        if n == 0 {
            return 0
        }

        var leftMax = [Int](repeating: 0, count: n)
        var rightMax = [Int](repeating: 0, count: n)

        leftMax[0] = height[0]
        for i in 1..<n {
            leftMax[i] = max(leftMax[i - 1], height[i])
        }

        rightMax[n - 1] = height[n - 1]
        for i in stride(from: n - 2, through: 0, by: -1) {
            rightMax[i] = max(rightMax[i + 1], height[i])
        }

        var res = 0
        for i in 0..<n {
            res += min(leftMax[i], rightMax[i]) - height[i]
        }
        return res
    }
}

impl Solution {
    pub fn trap(height: Vec<i32>) -> i32 {
        let n = height.len();
        if n == 0 {
            return 0;
        }

        let mut left_max = vec![0; n];
        let mut right_max = vec![0; n];

        left_max[0] = height[0];
        for i in 1..n {
            left_max[i] = left_max[i - 1].max(height[i]);
        }

        right_max[n - 1] = height[n - 1];
        for i in (0..n - 1).rev() {
            right_max[i] = right_max[i + 1].max(height[i]);
        }

        let mut res = 0;
        for i in 0..n {
            res += left_max[i].min(right_max[i]) - height[i];
        }
        res
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Stack

Intuition

The stack helps us find places where water can collect.
When we see a bar that is taller than the bar on top of the stack, it means we've found a right wall for a container.
The bar we pop is the bottom, and the new top of the stack becomes the left wall.
With a left wall, bottom, and right wall, we can calculate how much water fits in between.
We keep doing this as long as the current bar keeps forming valid containers.

Algorithm

Create an empty stack and set res = 0.
Loop through each index i:
- While the stack is not empty and height[i] is taller than the bar at the stack's top:
  - Pop the top index — that's the bottom.
  - If the stack is not empty:
    - Compute the trapped water between the new top (left wall) and the current bar (right wall).
    - Add it to res.
- Push the current index onto the stack.
Return res after the loop finishes.

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0
        stack = []
        res = 0

        for i in range(len(height)):
            while stack and height[i] >= height[stack[-1]]:
                mid = height[stack.pop()]
                if stack:
                    right = height[i]
                    left = height[stack[-1]]
                    h = min(right, left) - mid
                    w = i - stack[-1] - 1
                    res += h * w
            stack.append(i)
        return res

public class Solution {
    public int trap(int[] height) {
        if (height.length == 0) {
            return 0;
        }

        Stack<Integer> stack = new Stack<>();
        int res = 0;

        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[i] >= height[stack.peek()]) {
                int mid = height[stack.pop()];
                if (!stack.isEmpty()) {
                    int right = height[i];
                    int left = height[stack.peek()];
                    int h = Math.min(right, left) - mid;
                    int w = i - stack.peek() - 1;
                    res += h * w;
                }
            }
            stack.push(i);
        }
        return res;
    }
}

class Solution {
public:
    int trap(vector<int>& height) {
        if (height.empty()) {
            return 0;
        }

        stack<int> stk;
        int res = 0;

        for (int i = 0; i < height.size(); i++) {
            while (!stk.empty() && height[i] >= height[stk.top()]) {
                int mid = height[stk.top()];
                stk.pop();
                if (!stk.empty()) {
                    int right = height[i];
                    int left = height[stk.top()];
                    int h = min(right, left) - mid;
                    int w = i - stk.top() - 1;
                    res += h * w;
                }
            }
            stk.push(i);
        }

        return res;
    }
};

class Solution {
    /**
     * @param {number[]} height
     * @return {number}
     */
    trap(height) {
        if (height.length === 0) {
            return 0;
        }

        const stack = [];
        let res = 0;

        for (let i = 0; i < height.length; i++) {
            while (
                stack.length > 0 &&
                height[i] >= height[stack[stack.length - 1]]
            ) {
                const mid = height[stack.pop()];
                if (stack.length > 0) {
                    const right = height[i];
                    const left = height[stack[stack.length - 1]];
                    const h = Math.min(right, left) - mid;
                    const w = i - stack[stack.length - 1] - 1;
                    res += h * w;
                }
            }
            stack.push(i);
        }
        return res;
    }
}

public class Solution {
    public int Trap(int[] height) {
        if (height.Length == 0) {
            return 0;
        }

        Stack<int> stack = new Stack<int>();
        int res = 0;

        for (int i = 0; i < height.Length; i++) {
            while (stack.Count > 0 && height[i] >= height[stack.Peek()]) {
                int mid = height[stack.Pop()];
                if (stack.Count > 0) {
                    int right = height[i];
                    int left = height[stack.Peek()];
                    int h = Math.Min(right, left) - mid;
                    int w = i - stack.Peek() - 1;
                    res += h * w;
                }
            }
            stack.Push(i);
        }
        return res;
    }
}

func trap(height []int) int {
    if len(height) == 0 {
        return 0
    }

    stack := linkedliststack.New()
    res := 0

    for i := 0; i < len(height); i++ {
        for !stack.Empty() {
            topIndex, _ := stack.Peek()
            if height[i] >= height[topIndex.(int)] {
                midIndex, _ := stack.Pop()
                mid := height[midIndex.(int)]
                if !stack.Empty() {
                    topIndex, _ := stack.Peek()
                    right := height[i]
                    left := height[topIndex.(int)]
                    h := min(right, left) - mid
                    w := i - topIndex.(int) - 1
                    res += h * w
                }
            } else {
                break
            }
        }
        stack.Push(i)
    }
    return res
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

class Solution {
    fun trap(height: IntArray): Int {
        if (height.isEmpty()) return 0

        val stack = ArrayDeque<Int>()
        var res = 0

        for (i in height.indices) {
            while (stack.isNotEmpty() && height[i] >= height[stack.first()]) {
                val mid = stack.removeFirst()
                if (stack.isNotEmpty()) {
                    val left = stack.first()
                    val right = height[i]
                    val h = minOf(right, height[left]) - height[mid]
                    val w = i - left - 1
                    res += h * w
                }
            }
            stack.addFirst(i)
        }
        return res
    }
}

class Solution {
    func trap(_ height: [Int]) -> Int {
        if height.isEmpty {
            return 0
        }
        var stack = [Int]()
        var res = 0

        for i in 0..<height.count {
            while !stack.isEmpty && height[i] >= height[stack.last!] {
                let mid = height[stack.removeLast()]
                if !stack.isEmpty {
                    let right = height[i]
                    let left = height[stack.last!]
                    let h = min(right, left) - mid
                    let w = i - stack.last! - 1
                    res += h * w
                }
            }
            stack.append(i)
        }
        return res
    }
}

impl Solution {
    pub fn trap(height: Vec<i32>) -> i32 {
        if height.is_empty() {
            return 0;
        }

        let mut stack: Vec<usize> = Vec::new();
        let mut res = 0;

        for i in 0..height.len() {
            while let Some(&top) = stack.last() {
                if height[i] >= height[top] {
                    let mid = height[stack.pop().unwrap()];
                    if let Some(&left_idx) = stack.last() {
                        let right = height[i];
                        let left = height[left_idx];
                        let h = right.min(left) - mid;
                        let w = (i - left_idx - 1) as i32;
                        res += h * w;
                    }
                } else {
                    break;
                }
            }
            stack.push(i);
        }
        res
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

4. Two Pointers

Intuition

Water at any position depends on the shorter wall between the left and right sides.
So if the left wall is shorter, the right wall can't help us—water is limited by the left side.
That means we safely move the left pointer inward and calculate how much water can be trapped there.
Similarly, if the right wall is shorter, we move the right pointer left.

As we move the pointers, we keep track of the highest wall seen so far on each side (leftMax and rightMax).
The water at each position is simply:

max wall on that side – height at that position

Algorithm

Set two pointers:
- l at the start
- r at the end
  Track leftMax and rightMax as the tallest walls seen.
While l < r:
- If leftMax < rightMax:
  - Move l right.
  - Update leftMax.
  - Add leftMax - height[l] to the result.
- Else:
  - Move r left.
  - Update rightMax.
  - Add rightMax - height[r] to the result.
Return the total trapped water.

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0

        l, r = 0, len(height) - 1
        leftMax, rightMax = height[l], height[r]
        res = 0
        while l < r:
            if leftMax < rightMax:
                l += 1
                leftMax = max(leftMax, height[l])
                res += leftMax - height[l]
            else:
                r -= 1
                rightMax = max(rightMax, height[r])
                res += rightMax - height[r]
        return res

public class Solution {
    public int trap(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }

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

class Solution {
public:
    int trap(vector<int>& height) {
        if (height.empty()) {
            return 0;
        }

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

class Solution {
    /**
     * @param {number[]} height
     * @return {number}
     */
    trap(height) {
        if (!height || height.length === 0) {
            return 0;
        }

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

public class Solution {
    public int Trap(int[] height) {
        if (height == null || height.Length == 0) {
            return 0;
        }

        int l = 0, r = height.Length - 1;
        int leftMax = height[l], rightMax = height[r];
        int res = 0;
        while (l < r) {
            if (leftMax < rightMax) {
                l++;
                leftMax = Math.Max(leftMax, height[l]);
                res += leftMax - height[l];
            } else {
                r--;
                rightMax = Math.Max(rightMax, height[r]);
                res += rightMax - height[r];
            }
        }
        return res;
    }
}

func trap(height []int) int {
    if len(height) == 0 {
        return 0
    }

    l, r := 0, len(height)-1
    leftMax, rightMax := height[l], height[r]
    res := 0

    for l < r {
        if leftMax < rightMax {
            l++
            leftMax = max(leftMax, height[l])
            res += leftMax - height[l]
        } else {
            r--
            rightMax = max(rightMax, height[r])
            res += rightMax - height[r]
        }
    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

class Solution {
    fun trap(height: IntArray): Int {
        if (height.isEmpty()) return 0

        var l = 0
        var r = height.size - 1
        var leftMax = height[l]
        var rightMax = height[r]
        var res = 0

        while (l < r) {
            if (leftMax < rightMax) {
                l++
                leftMax = maxOf(leftMax, height[l])
                res += leftMax - height[l]
            } else {
                r--
                rightMax = maxOf(rightMax, height[r])
                res += rightMax - height[r]
            }
        }
        return res
    }
}

class Solution {
    func trap(_ height: [Int]) -> Int {
        if height.isEmpty {
            return 0
        }

        var l = 0, r = height.count - 1
        var leftMax = height[l], rightMax = height[r]
        var res = 0

        while l < r {
            if leftMax < rightMax {
                l += 1
                leftMax = max(leftMax, height[l])
                res += leftMax - height[l]
            } else {
                r -= 1
                rightMax = max(rightMax, height[r])
                res += rightMax - height[r]
            }
        }
        return res
    }
}

impl Solution {
    pub fn trap(height: Vec<i32>) -> i32 {
        if height.is_empty() {
            return 0;
        }

        let mut l = 0;
        let mut r = height.len() - 1;
        let mut left_max = height[l];
        let mut right_max = height[r];
        let mut res = 0;

        while l < r {
            if left_max < right_max {
                l += 1;
                left_max = left_max.max(height[l]);
                res += left_max - height[l];
            } else {
                r -= 1;
                right_max = right_max.max(height[r]);
                res += right_max - height[r];
            }
        }
        res
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

Common Pitfalls

Calculating Water at Boundary Bars

The leftmost and rightmost bars can never hold water above them since there's no wall on one side to contain it. Including them in water calculations gives wrong results.

Using Current Bar Height Instead of Max Heights

Water at each position depends on the minimum of the maximum heights to its left and right, minus the current height. Using the current bar's height in the max comparison instead of tracking running maximums is incorrect.

# Wrong: comparing current height directly
water = min(height[l], height[r]) - height[i]
# Correct: use maximum heights seen so far
water = min(leftMax, rightMax) - height[i]

Negative Water Values

When the current bar is taller than the limiting wall, the water calculation yields a negative value. This happens at peaks and should contribute zero water, not negative.

# Wrong: can add negative water
res += leftMax - height[i]
# Correct: ensure non-negative
res += max(0, min(leftMax, rightMax) - height[i])

Wrong Pointer Movement in Two Pointers

In the two-pointer approach, always move the pointer on the side with the smaller max height. Moving the wrong pointer breaks the invariant that the smaller side determines the water level.