Problem Restatement or Summarize

Given an array height[0…n-1] ( length n ) of non-negative integers, each representing a bar of width 1. Compute the total units of water that can be trapped between the bars after it rains.

1. Brute-force baseline

For each index i, scan left to find the tallest bar to its left, scan right to find the tallest bar to its right, then calculate

water_at_i = max(0, min(max_left_at_i, max_right_at_i) - height[i])

pros: trivial to derive

cons: O(n2) in the worst case.

2. Precompute - arrays(DP-Style) - O(n) time, O(n) space

Core idea

Instead of rescanning on each i, we can reuse the result of the latest maximum in left (or right) we just calculate recently.

Implementation

# Build the array
maxLeft = [0]*n
for i in range(1, n):
    maxLeft[i] = max(maxLeft[i-1], height[i-1])

maxRight = [0]*n
for i in range(n-2, -1, -1):
    maxRight[i] = max(maxRight[i+1], height[i+1])
    
    
# at each step calculate
water_at_i = max(0, min(max_left_at_i, max_right_at_i) - height[i])

Pros: Debug easily, you can monitor at each step to see what the result is and compare with the example

Cons: we are using two extra arrays with the length of n , so its can be disaster.

3. Two-pointer technique - O(n) time, O(1) extra space

Core insight

At any position i, trapped water can calculate based on the smaller of two heighest length on left and right hands. The two pointers trick maintains two running maxima and gradually inward for both side. Focus on three points:

• Pointers

  • l starts at 0, r at n−1.

• Running maxima

  • leftMax = max height seen so far from the left up to l.
  • rightMax = max height seen so far from the right down to r.

• Key decision at each step

  Compare height[l] vs. height[r]:

  • If height[l] ≤ height[r], then left side is the bottleneck (limiting wall) for index l.
  • Else, right side is the bottleneck for index r.

Why? When height[l] ≤ height[r], you are guaranteed that some bar to the right (namely at r) is at least as tall as height[l]. Therefore the limiting wall for l is leftMax, and you can safely compute

water_at_l = leftMax – height[l]

without ever needing the full right-side max array.

Pseudocode

java
Sao chépChỉnh sửa
int l = 0, r = n − 1;
int leftMax = 0, rightMax = 0;
int trapped = 0;

while (l ≤ r) {
  if (height[l] ≤ height[r]) {
    // process l
    leftMax = max(leftMax, height[l]);
    trapped += leftMax − height[l];
    l++;
  } else {
    // process r
    rightMax = max(rightMax, height[r]);
    trapped += rightMax − height[r];
    r--;
  }
}
return trapped;

Detailed Run

Let’s go through [0,3,0,2,0,4] (res = 7)

Why It’s Correct

• Whenever you process the lower side pointer, you know the opposite side pointer guarantees a wall at least as tall for bounding water.
• By updating leftMax only when height[l] ≤ height[r], you maintain the invariant leftMax ≤ rightMax. Thus min(leftMax, rightMax) = leftMax, and computing leftMax − height[l] is valid.

Pros: Use linear time with O(1) space - The optimized one Cons: you need to keep invariant through all the times

In Summary

• Brute-force is simplest to derive but quadratic.
• Precompute-arrays hits linear time with linear extra space—great for clarity.
• Two-pointer achieves linear time and constant space by leveraging the fact that the lower of the two pointers at each step is the true limiting wall for water at that position.