Pacific Atlantic Water Flow: đảo ngược dòng chảy để tìm khả năng tiếp cận

Setup của bài toán rất thanh lịch. Một hòn đảo nằm giữa hai đại dương: Pacific ở cạnh trên và cạnh trái, Atlantic ở cạnh dưới và cạnh phải. Mưa rơi, nước chảy xuống (hoặc di chuyển ngang bằng), và bạn muốn tìm mọi ô có thể chảy đến cả hai đại dương. Đi xuôi từ mỗi ô đến cả hai đại dương — đó là cách đọc trực quan. Và cũng là cách chậm nhất.

Insight then chốt là water flow có thể đảo ngược theo cách hữu ích. Thay vì hỏi "nước từ ô này có thể chảy đến biên Pacific không?", hãy hỏi "nước từ biên Pacific có thể chảy đến ô này không?" Điều kiện chỉ lật ngược lại: thay vì yêu cầu ô kề <= ô hiện tại (chảy xuống), bạn yêu cầu nó >= (đi ngược lên). Bắt đầu DFS từ mọi ô đang tiếp giáp đại dương và lan vào bên trong. Bất kỳ ô nào có thể đến được từ DFS của Pacific và cũng đến được từ DFS của Atlantic đều là đáp án hợp lệ.

Đó là toàn bộ idea. Mọi thứ bên dưới là làm cho nó chính xác và hiệu quả.

Đề bài

Cho một hòn đảo hình chữ nhật m x n tiếp giáp Thái Bình Dương (Pacific Ocean) ở cạnh trái và cạnh trên, Đại Tây Dương (Atlantic Ocean) ở cạnh phải và cạnh dưới. Ma trận số nguyên heights cho biết độ cao của từng ô, trong đó nước chỉ có thể chảy sang ô kề (bắc, nam, đông, tây) nếu độ cao của ô đó nhỏ hơn hoặc bằng ô hiện tại. Trả về tất cả các ô mà nước mưa từ đó có thể chảy đến cả hai đại dương. Đề bài đầy đủ: LeetCode 417.

Ràng buộc:
- m == heights.length
- n == heights[r].length
- 1 <= m, n <= 200
- 0 <= heights[r][c] <= 10^5

Constraints buộc bạn phải làm gì

Grid có kích thước m x n với 1 <= m, n <= 200. Số ô tối đa là 40.000, và brute force sẽ là 40.000 * 40.000 = 1.6 * 10^9 phép toán — rõ ràng quá chậm. O(mn) là mục tiêu, và hoàn toàn đạt được.

Các height nằm trong [0, 10^5]. Không có số âm nên không có thủ thuật về dấu. Giá trị có thể bằng nhau — nước có thể chảy giữa các ô cùng độ cao — đó là lý do điều kiện là >= chứ không phải > nghiêm ngặt. Ranh giới này (plateau) hay làm người ta vấp khi viết > thay vì >=.

Grid luôn có ít nhất 1x1. Trường hợp m = n = 1 thì ô duy nhất đó tiếp giáp tất cả bốn cạnh cùng lúc — hiển nhiên nó có thể đến cả hai đại dương. Code không được special-case điều này; nó phải tự nhiên rơi ra từ logic chung.

Approach 1: Brute force — DFS từ mỗi ô

Với mỗi ô (r, c), chạy hai DFS độc lập: một để kiểm tra ô đó có thể chảy đến Pacific không, một cho Atlantic. DFS chỉ di chuyển đến ô kề khi height của ô kề <= height hiện tại (nước chảy xuống). Một ô "đến" được đại dương nếu DFS bước vào một ô biên tiếp giáp đại dương đó.

class Solution:
    def pacificAtlantic(self, heights: list[list[int]]) -> list[list[int]]:
        if not heights or not heights[0]:
            return []
 
        m, n = len(heights), len(heights[0])
        result = []
 
        def can_reach(r: int, c: int, ocean: str) -> bool:
            visited: set[tuple[int, int]] = set()
 
            def dfs(row: int, col: int) -> bool:
                if (row, col) in visited:
                    return False
                if ocean == "pacific":
                    if row == 0 or col == 0:
                        return True
                else:
                    if row == m - 1 or col == n - 1:
                        return True
                visited.add((row, col))
                for dr, dc in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
                    nr, nc = row + dr, col + dc
                    if 0 <= nr < m and 0 <= nc < n and heights[nr][nc] <= heights[row][col]:
                        if dfs(nr, nc):
                            return True
                return False
 
            return dfs(r, c)
 
        for i in range(m):
            for j in range(n):
                if can_reach(i, j, "pacific") and can_reach(i, j, "atlantic"):
                    result.append([i, j])
 
        return result

public class Solution {
    public IList<IList<int>> PacificAtlantic(int[][] heights) {
        if (heights == null || heights.Length == 0 || heights[0].Length == 0)
            return new List<IList<int>>();
 
        int m = heights.Length, n = heights[0].Length;
        var result = new List<IList<int>>();
 
        bool CanReach(int r, int c, string ocean) {
            var visited = new HashSet<(int, int)>();
 
            bool Dfs(int row, int col) {
                if (visited.Contains((row, col))) return false;
                if (ocean == "pacific") {
                    if (row == 0 || col == 0) return true;
                } else {
                    if (row == m - 1 || col == n - 1) return true;
                }
                visited.Add((row, col));
                int[,] dirs = { {0,1}, {1,0}, {0,-1}, {-1,0} };
                for (int d = 0; d < 4; d++) {
                    int nr = row + dirs[d, 0], nc = col + dirs[d, 1];
                    if (nr >= 0 && nr < m && nc >= 0 && nc < n
                        && heights[nr][nc] <= heights[row][col]) {
                        if (Dfs(nr, nc)) return true;
                    }
                }
                return false;
            }
 
            return Dfs(r, c);
        }
 
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (CanReach(i, j, "pacific") && CanReach(i, j, "atlantic"))
                    result.Add(new List<int> { i, j });
 
        return result;
    }
}

Complexity. Time: O(m^2 * n^2). Với mỗi trong số m*n ô, bạn chạy hai DFS, mỗi DFS có thể visit toàn bộ m*n ô. Space: O(mn) cho visited set trong mỗi DFS, cộng O(mn) call stack trong trường hợp xấu nhất. Quá chậm trên grid 200x200 nhưng đúng về mặt conceptual.

Brute force còn ẩn một sự dư thừa tinh tế: nếu (0, 3) đã được reach được từ (1, 3) khi đi đến Pacific, và sau đó bạn kiểm tra (2, 3) đi qua (1, 3), bạn lặp lại toàn bộ công việc đó mà không có caching. Reverse approach loại bỏ điều này hoàn toàn.

Approach 2: Reverse boundary DFS — approach dùng được trong thực tế

Insight về reversal: thay vì hỏi liệu một ô có thể chảy đến đại dương không, hãy hỏi đại dương có thể chảy ngược đến ô đó không. Chạy hai DFS pass riêng biệt: một bắt đầu từ mọi ô biên Pacific, một từ mọi ô biên Atlantic. Trong các reversed DFS pass này, bạn chỉ di chuyển đến ô kề nếu height của nó >= ô hiện tại (vì theo chiều thật, nước sẽ chảy từ ô kề xuống đến chúng ta — điều đó chỉ hợp lệ khi ô kề có height ít nhất bằng chúng ta).

Đánh dấu mọi ô có thể đến được từ biên Pacific vào boolean grid pac, và mọi ô đến được từ biên Atlantic vào atl. Đáp án là tất cả các ô mà cả hai đều được đánh dấu true.

class Solution:
    def pacificAtlantic(self, heights: list[list[int]]) -> list[list[int]]:
        if not heights or not heights[0]:
            return []
 
        m, n = len(heights), len(heights[0])
        pac = [[False] * n for _ in range(m)]
        atl = [[False] * n for _ in range(m)]
 
        def dfs(row: int, col: int, reachable: list[list[bool]], prev_height: int) -> None:
            if (row < 0 or row >= m or col < 0 or col >= n
                    or reachable[row][col]
                    or heights[row][col] < prev_height):
                return
            reachable[row][col] = True
            for dr, dc in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
                dfs(row + dr, col + dc, reachable, heights[row][col])
 
        # Seed từ biên Pacific (hàng trên + cột trái)
        for i in range(m):
            dfs(i, 0, pac, heights[i][0])
        for j in range(n):
            dfs(0, j, pac, heights[0][j])
 
        # Seed từ biên Atlantic (hàng dưới + cột phải)
        for i in range(m):
            dfs(i, n - 1, atl, heights[i][n - 1])
        for j in range(n):
            dfs(m - 1, j, atl, heights[m - 1][j])
 
        return [[i, j] for i in range(m) for j in range(n)
                if pac[i][j] and atl[i][j]]

public class Solution {
    public IList<IList<int>> PacificAtlantic(int[][] heights) {
        if (heights == null || heights.Length == 0 || heights[0].Length == 0)
            return new List<IList<int>>();
 
        int m = heights.Length, n = heights[0].Length;
        bool[,] pac = new bool[m, n];
        bool[,] atl = new bool[m, n];
 
        void Dfs(int row, int col, bool[,] reachable, int prevHeight) {
            if (row < 0 || row >= m || col < 0 || col >= n
                || reachable[row, col]
                || heights[row][col] < prevHeight)
                return;
            reachable[row, col] = true;
            int[,] dirs = { {0,1}, {1,0}, {0,-1}, {-1,0} };
            for (int d = 0; d < 4; d++)
                Dfs(row + dirs[d,0], col + dirs[d,1], reachable, heights[row][col]);
        }
 
        // Seed từ biên Pacific
        for (int i = 0; i < m; i++) Dfs(i, 0, pac, heights[i][0]);
        for (int j = 0; j < n; j++) Dfs(0, j, pac, heights[0][j]);
 
        // Seed từ biên Atlantic
        for (int i = 0; i < m; i++) Dfs(i, n - 1, atl, heights[i][n - 1]);
        for (int j = 0; j < n; j++) Dfs(m - 1, j, atl, heights[m - 1][j]);
 
        var result = new List<IList<int>>();
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (pac[i, j] && atl[i, j])
                    result.Add(new List<int> { i, j });
        return result;
    }
}

Complexity. Time: O(mn). Mỗi ô được visit tối đa một lần trong mỗi DFS pass, và có hai pass. Space: O(mn) cho hai boolean grid cộng O(mn) call stack trong trường hợp xấu nhất.

Trace tay qua ví dụ quan trọng

Lấy heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]] (grid 5x5 từ Example 1).

Biên Pacific được seed: toàn bộ cột trái (cột 0) và toàn bộ hàng trên (hàng 0). Từ đó, reversed DFS đánh dấu bất kỳ ô nào có thể đến được bằng cách đi ngược lên.

Sau DFS Pacific, pac trông như sau (T = reachable, F = không):

T T T T T
T T T T T
T T T F F
T T F F F
T F F F F

Biên Atlantic được seed: toàn bộ cột phải (cột 4) và toàn bộ hàng dưới (hàng 4). Sau DFS Atlantic, atl:

F F F T T
F F T T T
F T T T T
T T F T T
T T T T T

Giao của hai grid, các ô mà cả hai đều là T:

F F F T T   -> (0,4)
F F T T T   -> (1,3), (1,4)
F T T F F   -> (2,2)   (atl có (2,1)=T nhưng pac có (2,1)=F)
T T F F F   -> (3,0), (3,1)
T F F F F   -> (4,0)

Kết quả là [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]], khớp chính xác với expected output.

Trace thủ công ô (2, 2) với height 5 để cụ thể hơn. DFS Pacific reach ô này vì từ biên Pacific tại (0, 0) (height 1), bạn có thể đi đến (1, 0) (height 3), đến (2, 1) (height 4), đến (2, 2) (height 5) — mỗi bước đến ô có height >= ô trước (ngược lên trong chiều đảo, nghĩa là xuôi xuống trong chiều thật). DFS Atlantic reach (2, 2) qua (2, 4) (height 1) -> (2, 3) (height 3) -> (2, 2) (height 5). Vậy ô (2, 2) xứng đáng có mặt trong kết quả.

Các edge case cần chú ý

Grid 1x1. Ô duy nhất tiếp giáp tất cả bốn cạnh cùng lúc — cả pac và atl đều được đánh dấu true sau lần gọi DFS đầu tiên, trước khi DFS kịp recurse. Kết quả: [[0,0]]. Không cần special case.

Tất cả ô cùng height. Mọi ô có thể chảy đến mọi ô khác vì điều kiện là >= (height bằng nhau được chấp nhận). DFS từ biên Pacific lan khắp toàn bộ grid, DFS từ biên Atlantic cũng vậy. Mọi ô xuất hiện trong kết quả. Code xử lý đúng vì heights[neighbor] >= prev_height thỏa mãn ở khắp nơi.

Tăng đơn điệu từ trên-trái xuống dưới-phải. Chỉ các ô ở hàng trên và cột phải mới có thể reach cả hai đại dương. Ô góc trên-phải (0, n-1) hiển nhiên tiếp giáp cả hai. Hai DFS pass sẽ tự nhiên cho ra giao đúng mà không cần off-by-one.

Height 0 ở khắp nơi. Tương tự trường hợp cùng height. Mọi ô đều ra kết quả.

m = 1 hoặc n = 1 (một hàng hoặc một cột duy nhất). Nếu m = 1, hàng duy nhất đó tiếp giáp cả hai đại dương (Pacific ở trên, Atlantic ở dưới — cùng một hàng). Toàn bộ hàng xuất hiện trong kết quả. Boundary seeding bao phủ toàn bộ hàng cho cả hai DFS pass.

Bẫy >= vs >. Nếu bạn viết điều kiện dừng là heights[row][col] < prev_height nghiêm ngặt (thực ra đây đã đúng), nhưng nhầm thành heights[nr][nc] > heights[row][col] trong vòng lặp DFS forward thay vì >=, bạn sẽ chặn di chuyển ngang qua plateau cùng height. Ô (2,0) trong ví dụ có height 2, (1,0) có height 3. Trong reverse DFS từ Pacific, bạn đi từ (2,0) lên (1,0): height ô kề là 3 >= 2. Điều kiện > nghiêm ngặt sẽ chặn điều này. Luôn dùng >= trong điều kiện reverse.

Brute force hay reverse DFS — cái nào thực sự ship được

Tôi chọn reverse DFS không do dự. Chênh lệch thời gian không phải biên tế — là O(m^2 n^2) so với O(mn), trên grid 200x200 là xấp xỉ 1.6 tỷ phép toán so với 40.000. Dung lượng bộ nhớ như nhau cho cả hai. Chi phí duy nhất là việc lật ngược intuition, thứ chỉ cần một câu để giải thích trong code review: "chúng ta chạy DFS ngược từ mỗi biên đại dương và lấy giao của các tập reachable."

Brute force có chỗ đứng như một bước tư duy — nó làm cho lập luận correctness trở nên hiển nhiên — nhưng không bao giờ nên ship.

Pattern bên dưới: multi-source reverse reachability

Cấu trúc cốt lõi ở đây là multi-source BFS/DFS với điều kiện đảo ngược. Một lớp lớn bài toán grid hỏi "những ô nào có thể đến được một tập ô biên nào đó?" và câu trả lời hiệu quả luôn là: "đảo chiều, seed từ tập biên, lan vào bên trong." Key transfer:

• Theo chiều xuôi: di chuyển đến ô kề nếu heights[neighbor] <= heights[current] (nước chảy xuống).
• Theo chiều ngược: di chuyển đến ô kề nếu heights[neighbor] >= heights[current] (chúng ta leo lên để tìm ai có thể đã chảy đến chúng ta).

Bạn thấy cùng reversal này trong các bài về surrounded regions, enclaves, và disconnected components. Khi cần kiểm tra membership trong "các ô có thể đến được biên", luôn nghĩ: seed từ biên và hỏi "biên có thể đến ô này không?"

Cấu trúc hai-pass (một pass cho mỗi target set) cũng tổng quát hóa được. Ở đây có hai đại dương nên có hai pass. Nếu có ba target set, bạn chạy ba pass và intersect ba boolean grid. Chi phí O(k * mn) cho k target set là tuyến tính theo kích thước grid với bất kỳ k cố định nào.

Vị trí trong series graphs

Đây là bài thứ năm trong series graphs, sau Number of Islands (200), Clone Graph (133), Course Schedule (207), và Rotting Oranges (994). Các bài đó đã thiết lập các core traversal pattern: flood fill, BFS layered expansion, cycle detection qua DFS coloring, và multi-source BFS cho minimum distance. Pacific Atlantic thêm một pattern mới lên nền tảng đó — reverse reachability từ boundary set — về bản chất khác với cả bốn bài trước.

Bốn bài anh chị em dùng cùng reversal hoặc mở rộng nó:

Number of Enclaves (1020). Tìm các ô không thể đi ra khỏi biên grid. Cùng reversal: DFS từ mọi ô biên, đánh dấu các ô reachable, rồi đếm các ô chưa bao giờ được đánh dấu. Cấu trúc "reverse từ biên" hoàn toàn giống; chỉ câu hỏi (đếm so với thu thập tọa độ) thay đổi.

Surrounded Regions (130). Đánh dấu tất cả ô O trên biên và lan vào bên trong; mọi thứ không được đánh dấu bị bao quanh hoàn toàn và đổi thành X. Thêm một boundary-seed-then-invert pattern nữa. Khác với Pacific Atlantic ở chỗ chỉ có một biên (cạnh grid) thay vì hai biên rời nhau.

Rotting Oranges (994). Multi-source BFS từ tất cả ô rotten ban đầu cùng lúc. Không cần reversal vì source và target đều nằm trong nội vi — nhưng logic "seed từ nhiều nguồn cùng lúc" là cùng cấu trúc. So sánh điều này với việc seed tất cả ô biên Pacific cùng lúc cho DFS của Pacific.

Making a Large Island (827). Hai-pass: DFS đầu tiên để label mỗi island component với một id, rồi quét qua các ô bridge tiềm năng. Không phải strict reversal, nhưng cấu trúc "hai DFS pass trên cùng một grid để tính toán thông tin giao nhau" rhymes trực tiếp với Pacific Atlantic.