Pacific Atlantic Water Flow

1package pkg5leetcode.blind75;2 3/*4 * Pacific Atlantic Water Flow | LC 4175 * APPROACH: Reverse DFS/BFS from ocean borders; intersection cells drain both.6 * COMPLEXITY: Time O(mn), Space O(mn)7 */8import java.util.*;9 10public class blind75_LC417PacificAtlanticWaterFlow {11    static List<List<Integer>> pacificAtlantic(int[][] heights) {12        int m = heights.length, n = heights[0].length;13        boolean[][] pac = new boolean[m][n], atl = new boolean[m][n];14        for (int i = 0; i < m; i++) { dfs(heights, pac, i, 0); dfs(heights, atl, i, n - 1); }15        for (int j = 0; j < n; j++) { dfs(heights, pac, 0, j); dfs(heights, atl, m - 1, j); }16        List<List<Integer>> res = new ArrayList<>();17        for (int i = 0; i < m; i++)18            for (int j = 0; j < n; j++)19                if (pac[i][j] && atl[i][j]) res.add(Arrays.asList(i, j));20        return res;21    }22 23    static void dfs(int[][] h, boolean[][] vis, int r, int c) {24        vis[r][c] = true;25        int[][] d = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};26        for (int[] dd : d) {27            int nr = r + dd[0], nc = c + dd[1];28            if (nr >= 0 && nr < h.length && nc >= 0 && nc < h[0].length29                    && !vis[nr][nc] && h[nr][nc] >= h[r][c])30                dfs(h, vis, nr, nc);31        }32    }33 34    public static void main(String[] args) {35        int[][] grid = {{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}};36        List<List<Integer>> r = pacificAtlantic(grid);37        check(r.size() == 7, "size");38        check(r.contains(Arrays.asList(0, 4)), "cell1");39        System.out.println("all tests passed");40    }41 42    static void check(boolean cond, String name) {43        if (!cond) throw new AssertionError("FAILED: " + name);44        System.out.println("  PASS " + name);45    }46}