417. Pacific Atlantic Water Flow

Medium

Description

給定一個 m x n 的矩陣 heights 代表島嶼各位置的高度。水可以從高處往低處或等高處流動。太平洋在左邊和上邊，大西洋在右邊和下邊。找出所有能同時流向兩個大洋的座標。

Example:

Input: 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]] Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

Intuition#

反向思考：從海洋邊界出發逆流而上（往高處走），能到達的格子就是能流向該海洋的格子。兩個集合的交集即答案。

正向（從每個格子往海洋流）會有大量重複計算
反向從太平洋邊界和大西洋邊界各做一次 DFS/BFS
兩次搜尋都能到達的格子就是答案

Approaches#

1: BFS（從邊界出發）#

概念: 從太平洋和大西洋的邊界各做一次 BFS，逆流而上標記可達格子
時間複雜度: O(m * n)
空間複雜度: O(m * n)

class Solution {
    fun pacificAtlantic(heights: Array<IntArray>): List<List<Int>> {
        val m = heights.size
        val n = heights[0].size
        val pacific = Array(m) { BooleanArray(n) }
        val atlantic = Array(m) { BooleanArray(n) }
        val dirs = intArrayOf(0, 1, 0, -1, 0)

        fun bfs(starts: List<IntArray>, reachable: Array<BooleanArray>) {
            val queue: ArrayDeque<IntArray> = ArrayDeque()
            for (s in starts) {
                reachable[s[0]][s[1]] = true
                queue.add(s)
            }
            while (queue.isNotEmpty()) {
                val (r, c) = queue.removeFirst()
                for (d in 0 until 4) {
                    val nr = r + dirs[d]
                    val nc = c + dirs[d + 1]
                    if (nr in 0 until m && nc in 0 until n &&
                        !reachable[nr][nc] && heights[nr][nc] >= heights[r][c]) {
                        reachable[nr][nc] = true
                        queue.add(intArrayOf(nr, nc))
                    }
                }
            }
        }

        val pacStarts = mutableListOf<IntArray>()
        val atlStarts = mutableListOf<IntArray>()
        for (i in 0 until m) {
            pacStarts.add(intArrayOf(i, 0))
            atlStarts.add(intArrayOf(i, n - 1))
        }
        for (j in 0 until n) {
            pacStarts.add(intArrayOf(0, j))
            atlStarts.add(intArrayOf(m - 1, j))
        }

        bfs(pacStarts, pacific)
        bfs(atlStarts, atlantic)

        val result = mutableListOf<List<Int>>()
        for (i in 0 until m) {
            for (j in 0 until n) {
                if (pacific[i][j] && atlantic[i][j]) {
                    result.add(listOf(i, j))
                }
            }
        }
        return result
    }
}

⭐2: DFS（從邊界出發）#

概念: 從兩個海洋邊界各做一次 DFS，逆流而上標記，取交集
時間複雜度: O(m * n)
空間複雜度: O(m * n)

class Solution {
    fun pacificAtlantic(heights: Array<IntArray>): List<List<Int>> {
        val m = heights.size
        val n = heights[0].size
        val pacific = Array(m) { BooleanArray(n) }
        val atlantic = Array(m) { BooleanArray(n) }

        fun dfs(r: Int, c: Int, reachable: Array<BooleanArray>, prevHeight: Int) {
            if (r < 0 || r >= m || c < 0 || c >= n) return
            if (reachable[r][c] || heights[r][c] < prevHeight) return
            reachable[r][c] = true
            dfs(r + 1, c, reachable, heights[r][c])
            dfs(r - 1, c, reachable, heights[r][c])
            dfs(r, c + 1, reachable, heights[r][c])
            dfs(r, c - 1, reachable, heights[r][c])
        }

        for (i in 0 until m) {
            dfs(i, 0, pacific, heights[i][0])
            dfs(i, n - 1, atlantic, heights[i][n - 1])
        }
        for (j in 0 until n) {
            dfs(0, j, pacific, heights[0][j])
            dfs(m - 1, j, atlantic, heights[m - 1][j])
        }

        val result = mutableListOf<List<Int>>()
        for (i in 0 until m) {
            for (j in 0 until n) {
                if (pacific[i][j] && atlantic[i][j]) {
                    result.add(listOf(i, j))
                }
            }
        }
        return result
    }
}

🔑 Takeaways#

Pattern: 邊界反向搜尋 – 從終點倒推比從每個起點正向搜尋更高效
關鍵技巧: 逆流條件是 heights[nr][nc] >= heights[r][c]；兩次搜尋的交集即答案