to both the Pacific and Atlantic oceans.

Examples

Example 1:

$$ \Huge \begin{array}{c c c} \text{Pacific Ocean} & \begin{array}{|c|c|c|c|c|} \hline 1 & 2 & 2 & 3 & \colorbox{orange}5 \\ \hline 3 & 2 & 3 & \colorbox{orange}4 & \colorbox{orange}4 \\ \hline 2 & 4 & \colorbox{orange}5 & 3 & 1 \\ \hline \colorbox{orange}6 & \colorbox{orange}7 & 1 & 4 & 5 \\ \hline \colorbox{orange}5 & 1 & 1 & 2 & 4 \\ \hline \end{array} & \text{Atlantic Ocean} \end{array} $$

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]]

Example 2:

Input: heights = [[2,1],[1,2]]
Output: [[0,0],[0,1],[1,0],[1,1]]

Solution

Method 1 - BFS

We can see how many points can water flow to pacific point, and how many points can water flow to atlantic oceans. The intersection of these sets will the answer we want.

We can see first row is adjacent to Pacific ocean and last row is adjacent to Atlantic ocean. Likewise, first column is adjacent to pacific ocean and last column is adjacent to Atlantic ocean.

From these points we do BFS, so that we dont visit the same points again and again.

Approach

Here is the approach:

We identify the cells adjacent to the Pacific and Atlantic oceans:
- Cells in the first row and first column are adjacent to the Pacific Ocean.
- Cells in the last row and last column are adjacent to the Atlantic Ocean.
From these ocean-adjacent cells, we perform BFS to explore all cells reachable by water for that ocean.
At the end, the intersection of reachable cells from both oceans gives the desired result.
BFS ensures that we visit cells level by level, marking them as visited to avoid redundant visits.

Code

[{"language":"Java","code":"class Solution {\n    public List<List<Integer>> pacificAtlantic(int[][] heights) {\n        int m = heights.length, n = heights[0].length;\n        \n        // BFS function to compute reachable cells\n        Set<List<Integer>> bfs(List<int[]> starts) {\n            Set<List<Integer>> visited = new HashSet<>();\n            Queue<int[]> q = new LinkedList<>();\n            for (int[] start : starts) {\n                q.add(start);\n                visited.add(Arrays.asList(start[0], start[1]));\n            }\n            int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // Directions\n            \n            while (!q.isEmpty()) {\n                int[] cell = q.poll();\n                for (int[] d : dirs) {\n                    int x = cell[0] + d[0], y = cell[1] + d[1];\n                    if (x >= 0 && x < m && y >= 0 && y < n && !visited.contains(Arrays.asList(x, y)) && heights[x][y] >= heights[cell[0]][cell[1]]) {\n                        visited.add(Arrays.asList(x, y));\n                        q.offer(new int[] {x, y});\n                    }\n                }\n            }\n            return visited;\n        }\n        \n        // Starting points for Pacific and Atlantic\n        List<int[]> pac_starts = new ArrayList<>();\n        List<int[]> atl_starts = new ArrayList<>();\n        \n        for (int i = 0; i < m; i++) {\n            pac_starts.add(new int[] {i, 0});\n            atl_starts.add(new int[] {i, n - 1});\n        }\n        for (int j = 0; j < n; j++) {\n            pac_starts.add(new int[] {0, j});\n            atl_starts.add(new int[] {m - 1, j});\n        }\n        \n        // Find all cells reachable by each ocean\n

Related Tags