Classic two-pointer problem on LeetCode

Initial Approach

To accumulate water, each bar must have taller bars on both sides. Additionally, the water level above a bar is determined by the shorter of the two boundary bars — that is, the minimum of the left and right max heights minus the current bar's height.

The key challenge lies in identifying these boundary bars. A straightforward method would involve scanning through the array, marking the first non-zero bar as the left boundary. Once we encounter a bar equal to or taller than this left boundary, we mark it as the right boundary. Then, we can compute the trapped water between them. However, this approach requires multiple passes and becomes complicated when the tallest bar is in the middle.

In-Depth Analysis

Ideally, we want a single-pass solution where each bar contributes independently to the total trapped water. This means determining for each bar what its left and right maximum heights are.

We can precompute two arrays:

• One storing the maximum height from the left up to each position.
• Another storing the maximum height from the right down to each position.

Then, for each bar, calculate the trapped water using the formula: min(left_max, right_max) - current_height.

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

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

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

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

Further Optimization

Although the dynamic programming approach works well, it involves three traversals. Can we do better?

Given that the problem hints at using two pointers, let’s explore that direction.

The idea behind the two-pointer technique is that we always move the pointer pointing to the shorter bar because its water level is limited by its own side. As long as one side has a higher barrier, we know the water won’t spill over.

Steps:

1. Initialize left = 0, right = n - 1, maxLeft = 0, maxRight = 0, and totalWater = 0.
2. While left < right:

• If height[left] < height[right]:
• Water level is determined by maxLeft.
• If height[left] >= maxLeft, update maxLeft.
• Else, add maxLeft - height[left] to totalWater.
• Increment left.
• Otherwise:
• Water level is determined by maxRight.
• If height[right] >= maxRight, update maxRight.
• Else, add maxRight - height[right] to totalWater.
• Decrement right.

3. Return totalWater.

class Solution {
    public int trap(int[] height) {
        int total = 0;
        int left = 0, right = height.length - 1;
        int maxLeft = 0, maxRight = 0;

        while (left < right) {
            maxLeft = Math.max(maxLeft, height[left]);
            maxRight = Math.max(maxRight, height[right]);

            if (height[left] < height[right]) {
                total += maxLeft - height[left];
                ++left;
            } else {
                total += maxRight - height[right];
                --right;
            }
        }

        return total;
    }
}

Alternative Strategy: Monotonic Stack

Instead of computing water vertically per bar, consider calculating horizontally layer by layer.

This leads us to use a monotonic stack to track potential basins.

When traversing, if we see a sequence starting with decreasing heights followed by increasing ones, we can detect a basin. We push indices onto the stack during decreasing sequences and pop when encountering an increase.

Core Idea:

• Store indices in the stack such that corresponding heights are monotonically decreasing.
• When a taller bar is found, it forms a basin with the previous bars.
• Pop elements from the stack and compute the area of the formed basin.

Steps:

1. Initialize a stack and totalWater = 0.
2. For each index i:

• While stack is not empty and height[i] > height[stack.peek()]:
• Pop the top element (bottomIndex) and check if stack is empty.
• If not empty, compute width and height of the basin.
• Add width × height to totalWater.
• Push i into the stack.

3. Return totalWater.

class Solution {
public int trap(int[] height) {
int total = 0;
Deque stack = new LinkedList();
int n = height.length;

for (int i = 0; i < n; ++i) {
while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
int bottom = stack.pop();
if (stack.isEmpty()) break;
int leftBoundary = stack.peek();
int width = i - leftBoundary - 1;
int minHeight = Math.min(height[leftBoundary], height[i]);
total += width * (minHeight - height[bottom]);
}
stack.push(i);
}

return total;
}
}