Trapping Rain Water: từ O(n) space xuống O(1) với two pointers

height = [0,1,0,2,1,0,1,3,2,1,2,1] — vẽ các cột ra, tô màu phần nước, đáp án là 6. Nhìn hình ảnh thì trông như bài toán hình học. Thực ra đây là câu hỏi về một cell đơn lẻ biết được gì: tại vị trí i, nước có thể dâng lên đến độ cao bao nhiêu? Mức nước bị giới hạn bởi cột ngắn hơn trong hai bức tường bao quanh nó — thanh cao nhất bên trái và thanh cao nhất bên phải. Mọi thứ còn lại đều xuất phát từ đó.

Công thức cho từng cell

Với mỗi vị trí i, lượng nước bị giữ lại phía trên nó là:

water[i] = max(0, min(left_max[i], right_max[i]) - height[i])

left_max[i] là độ cao lớn nhất trong height[0..i]. right_max[i] là độ cao lớn nhất trong height[i..n-1]. Bản thân cell là một phần của cả hai — nên cả hai max đều không bao giờ bằng không khi có cột. Tổng water[i] trên tất cả các vị trí cho ra đáp án. Công thức này là xương sống của mọi solution. Các approach chỉ khác nhau ở cách tính left_max và right_max hiệu quả đến mức nào.

Constraints buộc ta phải làm gì

n lên đến 20 000 và mỗi height lên đến 100 000. O(n²) với 400 triệu phép tính là quá tệ trên input 20 000 phần tử. O(n) mới là target thực sự. Giới hạn height không ảnh hưởng đến việc chọn thuật toán nhưng lại quan trọng với overflow: trong C#, tổng tối đa khi 20 000 cell mỗi cell giữ tới 100 000 đơn vị nước là gần 2 × 10^9, vừa khít trong int 32-bit. Nếu bài được scale lên thì cần dùng long.

Constraint thực sự định hình thuật toán là hệ quả từ n <= 2 * 10^4: bạn có thể dùng O(n) extra space (hai mảng 20 000 phần tử mỗi cái không đáng kể), nên cách prefix/suffix precomputation hoàn toàn khả thi. Câu hỏi sâu hơn là liệu có thể loại bỏ luôn O(n) space đó không — và two-pointer approach trả lời là được, với cái giá là argument về correctness khó hơn.

Mảng ngắn hơn 3 phần tử không thể giữ nước. Các edge case trả về 0 ngay: n < 3, input toàn số 0, mảng monotone (tăng dần hoặc giảm dần — không có valley). Cả bốn approach đều xử lý những trường hợp này mà không cần guard riêng — phép tính tích lũy đơn giản không ra gì.

Approach 1: brute force — O(n²) time, O(1) space

Với mỗi vị trí, duyệt sang trái tìm left_max, duyệt sang phải tìm right_max, rồi áp dụng công thức.

class Solution:
    def trap(self, height: list[int]) -> int:
        n = len(height)
        total = 0
        for i in range(1, n - 1):
            left_max = max(height[:i+1])
            right_max = max(height[i:])
            total += max(0, min(left_max, right_max) - height[i])
        return total

public class Solution {
    public int Trap(int[] height) {
        int n = height.Length;
        int total = 0;
        for (int i = 1; i < n - 1; i++) {
            int leftMax = 0;
            for (int j = 0; j <= i; j++)
                leftMax = Math.Max(leftMax, height[j]);
            int rightMax = 0;
            for (int j = i; j < n; j++)
                rightMax = Math.Max(rightMax, height[j]);
            total += Math.Max(0, Math.Min(leftMax, rightMax) - height[i]);
        }
        return total;
    }
}

Trace trên height = [4, 2, 0, 3, 2, 5] — chỉ các vị trí nội bộ:

i=1: left_max=max(4,2)=4, right_max=max(2,0,3,2,5)=5 -> min(4,5)-2 = 2
i=2: left_max=max(4,2,0)=4, right_max=max(0,3,2,5)=5 -> min(4,5)-0 = 4
i=3: left_max=max(4,2,0,3)=4, right_max=max(3,2,5)=5 -> min(4,5)-3 = 1
i=4: left_max=max(4,2,0,3,2)=4, right_max=max(2,5)=5 -> min(4,5)-2 = 2
total = 2 + 4 + 1 + 2 = 9

Đúng. Nhưng công việc bị lặp lại. left_max tại vị trí 3 tính lại tất cả những gì đã thấy tại vị trí 2. Mỗi vòng lặp bỏ đi running max của vòng trước đó.

Approach 2: prefix/suffix arrays — O(n) time, O(n) space

Precompute. Một lần duyệt trái-sang-phải fill left_max. Một lần duyệt phải-sang-trái fill right_max. Một lần duyệt cuối tích lũy nước. Ba vòng lặp O(n); không có công việc nào bị lặp lại.

Trace đầy đủ trên height = [0,1,0,2,1,0,1,3,2,1,2,1]:

Bước 1 — xây left_max (trái sang phải, mỗi cell = max đã thấy tính cả chính nó):
  i=0:  left_max[0] = height[0] = 0
  i=1:  left_max[1] = max(0, 1) = 1
  i=2:  left_max[2] = max(1, 0) = 1
  i=3:  left_max[3] = max(1, 2) = 2
  i=4:  left_max[4] = max(2, 1) = 2
  i=5:  left_max[5] = max(2, 0) = 2
  i=6:  left_max[6] = max(2, 1) = 2
  i=7:  left_max[7] = max(2, 3) = 3
  i=8..11: đều 3 (3 thống trị)
  -> left_max = [0,1,1,2,2,2,2,3,3,3,3,3]

Bước 2 — xây right_max (phải sang trái):
  i=11: right_max[11] = height[11] = 1
  i=10: right_max[10] = max(1, 2) = 2
  i=9:  right_max[9]  = max(2, 1) = 2
  i=8:  right_max[8]  = max(2, 2) = 2
  i=7:  right_max[7]  = max(2, 3) = 3
  i=6..0: đều 3
  -> right_max = [3,3,3,3,3,3,3,3,2,2,2,1]

Bước 3 — tích lũy (water = max(0, min(L, R) - h)):
  i=0:  min(0,3)-0 = 0
  i=1:  min(1,3)-1 = 0
  i=2:  min(1,3)-0 = 1  ***
  i=3:  min(2,3)-2 = 0
  i=4:  min(2,3)-1 = 1  ***
  i=5:  min(2,3)-0 = 2  ***
  i=6:  min(2,3)-1 = 1  ***
  i=7:  min(3,3)-3 = 0
  i=8:  min(3,2)-2 = 0
  i=9:  min(3,2)-1 = 1  ***
  i=10: min(3,2)-2 = 0
  i=11: min(3,1)-1 = 0
  total = 1+1+2+1+1 = 6 ✓

class Solution:
    def trap(self, height: list[int]) -> int:
        n = len(height)
        left_max = [0] * n
        right_max = [0] * n
 
        left_max[0] = height[0]
        for i in range(1, n):
            left_max[i] = max(left_max[i - 1], height[i])
 
        right_max[n - 1] = height[n - 1]
        for i in range(n - 2, -1, -1):
            right_max[i] = max(right_max[i + 1], height[i])
 
        total = 0
        for i in range(n):
            total += max(0, min(left_max[i], right_max[i]) - height[i])
        return total

public class Solution {
    public int Trap(int[] height) {
        int n = height.Length;
        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 total = 0;
        for (int i = 0; i < n; i++)
            total += Math.Max(0, Math.Min(leftMax[i], rightMax[i]) - height[i]);
        return total;
    }
}

Đây là version tôi dùng khi muốn code dễ đọc và dễ verify. Ba lần duyệt mỗi cái đều có invariant rõ ràng. Time là O(n) — optimal vì bạn phải kiểm tra mỗi thanh ít nhất một lần. Chi phí duy nhất là hai mảng phụ: O(n) space.

Với input 20 000 phần tử trong C#, hai int[] mỗi cái 20 000 phần tử chỉ là 160 KB. Không đáng kể. Nhưng câu hỏi liệu có thể làm tốt hơn tồn tại, và two-pointer approach trả lời được.

Approach 3: monotonic stack — O(n) time, O(n) space

Approach stack suy nghĩ khác đi. Thay vì hỏi "bao nhiêu nước nằm trên vị trí i?" theo từng cột, nó hỏi "khi nào một lớp nước nằm ngang đóng lại?" Nó xử lý nước theo từng lớp ngang thay vì từng cột dọc.

Stack lưu các index theo thứ tự chiều cao giảm dần (monotonically decreasing). Khi gặp một thanh cao hơn top của stack, một túi nước vừa đóng lại ở phía phải — thanh hiện tại là bức tường phải, stack top là đáy, và phần tử bên dưới trong stack là bức tường trái.

Trace từng bước trên height = [0,1,0,2,1,0,1,3,2,1,2,1], các bước chính:

i=0, h=0: stack=[] -> push 0. stack=[0]
i=1, h=1: h > height[0]=0
  pop bottom=0 (height=0), stack rỗng -> không có tường trái, break
  push 1. stack=[1]
i=2, h=0: h <= height[1]=1 -> push 2. stack=[1,2]
i=3, h=2: h > height[2]=0
  pop bottom=2 (height=0), left=stack[-1]=1 (height=1)
  width = 3-1-1 = 1, water_height = min(1,2)-0 = 1 -> cộng 1*1 = 1
  h > height[1]=1
  pop bottom=1 (height=1), stack rỗng -> break
  push 3. stack=[3]
i=4, h=1: h <= height[3]=2 -> push 4. stack=[3,4]
i=5, h=0: push 5. stack=[3,4,5]
i=6, h=1: h > height[5]=0
  pop bottom=5 (height=0), left=4 (height=1)
  width=6-4-1=1, water_height=min(1,1)-0=1 -> cộng 1
  h <= height[4]=1 -> push 6. stack=[3,4,6]
i=7, h=3: h > height[6]=1
  pop bottom=6 (height=1), left=4 (height=1)
  width=7-4-1=2, water_height=min(1,3)-1=0 -> cộng 0
  h > height[4]=1
  pop bottom=4 (height=1), left=3 (height=2)
  width=7-3-1=3, water_height=min(2,3)-1=1 -> cộng 3
  h > height[3]=2
  pop bottom=3 (height=2), stack rỗng -> break
  push 7. stack=[7]
...tiếp tục -> total = 6 ✓

class Solution:
    def trap(self, height: list[int]) -> int:
        stack = []
        total = 0
        for i, h in enumerate(height):
            while stack and h > height[stack[-1]]:
                bottom = stack.pop()
                if not stack:
                    break
                left = stack[-1]
                width = i - left - 1
                water_height = min(height[left], h) - height[bottom]
                total += width * water_height
            stack.append(i)
        return total

public class Solution {
    public int Trap(int[] height) {
        var stack = new Stack<int>();
        int total = 0;
        for (int i = 0; i < height.Length; i++) {
            while (stack.Count > 0 && height[i] > height[stack.Peek()]) {
                int bottom = stack.Pop();
                if (stack.Count == 0) break;
                int left = stack.Peek();
                int width = i - left - 1;
                int waterHeight = Math.Min(height[left], height[i]) - height[bottom];
                total += width * waterHeight;
            }
            stack.Push(i);
        }
        return total;
    }
}

Approach stack là O(n) time và O(n) space — cùng asymptotic profile với prefix arrays, nhưng tính nước theo chiều ngang thay vì chiều dọc. Nó tìm các container bị giới hạn khi chúng đóng lại, thay vì hỏi mỗi cell xem nó đầy đến đâu. Tôi sẽ không dùng nó trong interview trừ khi được hỏi cụ thể về stack variant — mental model khó dựng lại hơn dưới áp lực. Nhưng hiểu nó thì đáng vì cùng cách tư duy theo lớp ngang này giải quyết Largest Rectangle in Histogram (84), bài đối xứng của bài này.

State machine của stack cũng dễ lý luận theo dạng flowchart:

Approach 4: two pointers — O(n) time, O(1) space

Đây là insight khiến các prefix/suffix array trở nên không cần thiết. Nhìn lại công thức:

water[i] = max(0, min(left_max[i], right_max[i]) - height[i])

Nước tại vị trí i được xác định bởi min(left_max[i], right_max[i]). Minimum của hai maximum. Nếu left_max[i] < right_max[i], phía trái là constraint ràng buộc — không quan trọng right_max[i] chính xác là bao nhiêu, chỉ cần nó ít nhất bằng left_max[i]. Và nếu bạn đang xử lý từ trái với một pointer, và height[left] <= height[right], thì right_max cho vị trí left hiện tại đảm bảo ít nhất bằng height[right], tức là ít nhất bằng height[left]. Phía phải đủ cao; phía trái kiểm soát mức nước.

Đó là invariant: pointer nào đang trỏ vào thanh ngắn hơn, chúng ta có thể tính nước phía trên nó ngay lúc này chỉ bằng running max từ phía đó. Ta không cần biết chính xác max từ phía kia — chỉ cần biết nó ít nhất bằng, và height hiện tại của pointer kia đảm bảo điều đó.

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

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

Một lần duyệt. Bốn biến scalar. Hai running max thay thế hai mảng — nhưng chỉ vì chúng ta xử lý các vị trí theo thứ tự đảm bảo invariant luôn đúng ở mỗi bước.

Trace đầy đủ trên height = [4, 2, 0, 3, 2, 5]:

State: left=0, right=5, left_max=0, right_max=0, total=0

Bước 1: h[left]=h[0]=4, h[right]=h[5]=5. 4 <= 5 -> xử lý trái.
  h[0]=4 >= left_max=0 -> left_max = 4. left=1.
  total=0

Bước 2: h[1]=2, h[5]=5. 2 <= 5 -> xử lý trái.
  h[1]=2 < left_max=4 -> total += 4-2=2. left=2.
  total=2

Bước 3: h[2]=0, h[5]=5. 0 <= 5 -> xử lý trái.
  h[2]=0 < left_max=4 -> total += 4-0=4. left=3.
  total=6

Bước 4: h[3]=3, h[5]=5. 3 <= 5 -> xử lý trái.
  h[3]=3 < left_max=4 -> total += 4-3=1. left=4.
  total=7

Bước 5: h[4]=2, h[5]=5. 2 <= 5 -> xử lý trái.
  h[4]=2 < left_max=4 -> total += 4-2=2. left=5.
  total=9

left=5 == right=5. Dừng. Trả về 9. ✓

Ở bước 2, khi tính nước tại vị trí 1, chúng ta biết left_max=4 và biết height[right]=5 >= 4, nên right_max >= 5 >= 4 = left_max. Phía trái là constraint ràng buộc. Right max có thể là 5, 100, hay một triệu — không thay đổi kết quả. Ta không cần biết nó.

Các edge case thực sự đáng chú ý

Mỗi trường hợp dưới đây và tại sao code xử lý được — không cần guard riêng cho bất kỳ cái nào:

• height = [1] hoặc height = [1, 2]: điều kiện left < right của while loop sai ngay từ đầu, trả về 0. Đúng — một hoặc hai thanh không thể tạo valley.
• height = [0, 0, 0]: tất cả thanh bằng 0, left_max và right_max luôn bằng 0, total không bao giờ tăng. Trả về 0.
• height = [1, 2, 3, 4, 5] (tăng dần): right pointer luôn cao hơn, nên left luôn tiến. Tại mỗi bước height[left] >= left_max (nó tăng dần), nên cứ cập nhật left_max mà không cộng gì. Trả về 0.
• height = [5, 4, 3, 2, 1] (giảm dần): đối xứng — right luôn tiến, right_max cập nhật mỗi lần, không tích lũy gì. Trả về 0.
• height = [3, 0, 3] (hai tường bằng nhau): h[left]=3 <= h[right]=3, xử lý trái. h[0]=3 >= left_max=0, nên left_max=3, tiến. Rồi h[1]=0 <= h[right]=3, h[1]=0 < left_max=3, total += 3. Kết quả là 3. Công thức xử lý ties đúng vì cell được đưa vào chính max của nó — cả left_max lẫn right_max đều bao gồm vị trí 0 trong scan tương ứng.
• height = [2, 0, 2] (đối xứng): hai tường bằng nhau, nước lấp đầy cell giữa tới min(2,2)-0 = 2. Trả về 2.
• Tất cả bằng nhau, như height = [3, 3, 3, 3]: left_max luôn bằng height[left], nên cứ cập nhật max mà không tích lũy. Trả về 0 — mái bằng, không có valley.

Nên dùng cái nào

Two pointers cho production. Chênh lệch space — O(1) vs O(n) — không phải argument thực sự trên input 20 000 phần tử; argument là two-pointer version hoàn toàn vượt trội về resource và tương đương về tốc độ. Vấn đề là rõ ràng: invariant của two-pointer đòi hỏi lý luận về max phía còn lại phải là bao nhiêu, và điều đó không hiển nhiên với người đọc code lần đầu. Prefix/suffix arrays thì tự giải thích được.

Trong interview, tôi viết two pointers. Space win là bằng chứng mong đợi rằng bạn hiểu bài toán sâu sắc, không chỉ là có thể precompute arrays. Nếu interviewer hỏi tại sao nó đúng, bạn giải thích: phía ngắn hơn luôn có constraint đã biết đầy đủ; exact max của phía cao hơn không quan trọng, chỉ cần nó không phải bottleneck.

Monotonic stack tôi sẽ không đề xuất trước. Nó là O(n) time và O(n) space — cùng với prefix arrays nhưng khó đọc hơn. Giá trị của nó là hiểu nó sẽ chuyển trực tiếp sang Largest Rectangle in Histogram (84), đáng đầu tư.

So sánh các approach

Các bài liên quan

• Container With Most Water (11): Two pointers ở hai đầu của mảng height, mỗi bước di chuyển phía ngắn hơn vào trong. Quy tắc quyết định giống hệt về cấu trúc — luôn xử lý phía yếu hơn — nhưng ở đây bạn đang maximize area thay vì sum nước bị giữ lại. Nên làm ngay sau bài này; two-pointer skeleton gần như giống nhau.
• Largest Rectangle in Histogram (84): Bài đối xứng. Thay vì fill nước giữa các thanh, bạn tìm hình chữ nhật lớn nhất nằm dưới skyline. Monotonic stack từ Approach 3 chính xác là kỹ thuật giải 84 hiệu quả. Nếu stack variant của bài này làm bạn bối rối, giải 84 tiếp theo sẽ làm cả hai rõ hơn — cùng một pattern, hướng ngược lại.
• Trapping Rain Water II (407): Bản 3-D tổng quát. Grid 2-D thay vì mảng 1-D. Intuition cho từng cell vẫn giống nhau nhưng two-pointer trick không còn áp dụng; cần min-heap (priority queue) để luôn mở rộng từ cell boundary ngắn nhất. Quay lại sau khi nắm vững bản 1-D.
• Sum of Subarray Minimums (907): Dùng monotonic stack theo pattern "khi nào giá trị này không còn là constraint thống trị" tương tự. Củng cố lý luận stack-based mà không có framing nước.