Pacific Atlantic Water Flow

https://leetcode.com/problems/pacific-atlantic-water-flow/description/

Given anm x nmatrix of non-negative integers representing the height of each unit cell in a continent, the "Pacific ocean" touches the left and top edges of the matrix and the "Atlantic ocean" touches the right and bottom edges.

Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.

Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.

Thoughts

这题和01matrix很像, 只是不再要求distance最短了. 可以看作有两种点, matrix内的和matrix外的. 问能否从matrix内流向matrix外, 正常思路是从matrix内部开始检查. 但这样要一个个点查, 结果也不好复用. 因此我们可以从matrix外往内逆流而上, 检查所有能被matrix外点访问到的点. 分别执行这样的过程两次, 对应Pacific和Altantic. 然后再检查两个集合的交集即能流向两种边界的点的集合.

Code

class Solution {
    private Set<Integer> bfs(Queue<int[]> queue, int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        Set<Integer> reached = new HashSet<>();
        int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] pos = queue.poll();
                int height;
                if (pos[1] == -1 || pos[0] == -1 || pos[0] == m || pos[1] == n) {
                    height = 0;
                } else {
                    height = matrix[pos[0]][pos[1]];
                }

                for (int[] dir : dirs) {
                    int x = pos[0] + dir[0];
                    int y = pos[1] + dir[1];
                    int id = x * n + y;
                    if (reached.contains(id)) {
                        continue;
                    }
                    if (x >= 0 && x < m && y >= 0 && y < n) {
                        if (matrix[x][y] >= height) {
                            reached.add(id);
                            queue.add(new int[]{x, y});
                        }
                    }
                }
            }
        }
        return reached;
    }

    public List<int[]> pacificAtlantic(int[][] matrix) {
        List<int[]> res = new ArrayList<>();
        int m = matrix.length;
        if (m == 0) {
            return res;
        }
        int n = matrix[0].length;
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            queue.add(new int[]{i, -1});
        }
        for (int j = 0; j < n; j++) {
            queue.add(new int[]{-1, j});
        }
        Set<Integer> reachedByP = bfs(queue, matrix);
        queue.clear();
        for (int i = 0; i < m; i++) {
            queue.add(new int[]{i, n});
        }
        for (int j = 0; j < n; j++) {
            queue.add(new int[]{m, j});
        }
        Set<Integer> reachedByA = bfs(queue, matrix);


        for (Integer id : reachedByP) {
            if (reachedByA.contains(id)) {
                res.add(new int[]{id / n, id % n});
            }
        }

        return res;
    }
}

Analysis

时空复杂度都是O(MN).