LeetCode : 417. Pacific Atlantic Water Flow

[congr]

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

[congr]

[congr]

class Solution {
    List<int[]> list;
    public List<int[]> pacificAtlantic(int[][] matrix) {
        list = new ArrayList();
        if (matrix.length == 0) return list;

        int m = matrix.length, n = matrix[0].length;
        int[][] visited = new int[m][n];

        for (int i=0; i<m; i++) {
            dfs(matrix, i, 0, visited, 1);   // Pacific (left)     
            dfs(matrix, i, n-1, visited, 2); // Atlantic (right)
        }

        for (int j=0; j<n; j++) {
            dfs(matrix, 0, j, visited, 1);   // Pacific (left)     
            dfs(matrix, m-1, j, visited, 2); // Atlantic (right)
        }

        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++) {
                if (visited[i][j] == 3) list.add(new int[]{i,j});
            }
        }

        return list;
    }

    int[] dx = {0,1,0,-1};// D, R, U, L
    int[] dy = {1,0,-1,0};
    void dfs(int[][] matrix, int y, int x, int[][] visited, int mark) {
        if ((visited[y][x] & mark) == mark) return;
        visited[y][x] |= mark;

        for (int d = 0; d < 4; d++) {
            int ny = y+dy[d], nx = x+dx[d];
            if (inside(ny, nx, matrix) && matrix[ny][nx] >= matrix[y][x]) 
                dfs(matrix, ny, nx, visited, mark);
        }
    }

    boolean inside (int y, int x, int [][] matrix) {
        if (y >= 0 && x >= 0 && y < matrix.length && x < matrix[0].length) return true;
        else return false;
    }
}

[congr]

A bit optimized.

class Solution {
    List<int[]> list;
    public List<int[]> pacificAtlantic(int[][] matrix) {
        list = new ArrayList();
        if (matrix.length == 0) return list;

        int m = matrix.length, n = matrix[0].length;
        int[][] visited = new int[m][n];

        for (int i=0; i<m; i++) {
            dfs(matrix, i, 0, visited, 1);   // Pacific (left)     
            dfs(matrix, i, n-1, visited, 2); // Atlantic (right)
        }

        for (int j=0; j<n; j++) {
            dfs(matrix, 0, j, visited, 1);   // Pacific (left)     
            dfs(matrix, m-1, j, visited, 2); // Atlantic (right)
        }

        return list;
    }

    int[] dx = {0,1,0,-1};// D, R, U, L
    int[] dy = {1,0,-1,0};
    void dfs(int[][] matrix, int y, int x, int[][] visited, int mark) {
        if ((visited[y][x] & mark) == mark) return;
        visited[y][x] |= mark;

        if (visited[y][x] == 3)
            list.add(new int[] {y, x});

        for (int d = 0; d < 4; d++) {
            int ny = y+dy[d], nx = x+dx[d];
            if (inside(ny, nx, matrix) && matrix[ny][nx] >= matrix[y][x]) 
                dfs(matrix, ny, nx, visited, mark);
        }
    }

    boolean inside (int y, int x, int [][] matrix) {
        if (y >= 0 && x >= 0 && y < matrix.length && x < matrix[0].length) return true;
        else return false;
    }
}