LeetCode 417: Pacific Atlantic Water Flow Solution

Master LeetCode problem 417 (Pacific Atlantic Water Flow), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

417. Pacific Atlantic Water Flow

Medium

Array Depth-First Search Breadth-First Search Matrix

Problem Explanation

Explanation:

We can start from the borders of the island and perform a depth-first search (DFS) to mark all the cells that can flow to the Pacific Ocean and Atlantic Ocean separately.
We need two arrays to store whether a cell is reachable from the Pacific and Atlantic Oceans.
Finally, we iterate through all the cells to check if a cell is reachable from both oceans, and if so, add it to the result.

Algorithm:

Initialize two boolean arrays pacific and atlantic with dimensions m x n to store whether a cell is reachable from Pacific and Atlantic Oceans respectively.
Perform DFS from the border cells, marking all reachable cells for each ocean in the respective arrays.
Iterate through all cells and check if a cell is reachable from both oceans. If so, add it to the result.
Return the result.

Time Complexity: O(m x n) where m is the number of rows and n is the number of columns in the input matrix. Space Complexity: O(m x n) for the two boolean arrays.

Solution Code

class Solution {
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        List<List<Integer>> result = new ArrayList<>();
        if (heights == null || heights.length == 0 || heights[0].length == 0) {
            return result;
        }
        
        int m = heights.length;
        int n = heights[0].length;
        
        boolean[][] pacific = new boolean[m][n];
        boolean[][] atlantic = new boolean[m][n];
        
        for (int i = 0; i < m; i++) {
            dfs(heights, pacific, Integer.MIN_VALUE, i, 0);
            dfs(heights, atlantic, Integer.MIN_VALUE, i, n - 1);
        }
        
        for (int j = 0; j < n; j++) {
            dfs(heights, pacific, Integer.MIN_VALUE, 0, j);
            dfs(heights, atlantic, Integer.MIN_VALUE, m - 1, j);
        }
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pacific[i][j] && atlantic[i][j]) {
                    result.add(Arrays.asList(i, j));
                }
            }
        }
        
        return result;
    }
    
    private void dfs(int[][] heights, boolean[][] visited, int prevHeight, int i, int j) {
        if (i < 0 || i >= heights.length || j < 0 || j >= heights[0].length || visited[i][j] || heights[i][j] < prevHeight) {
            return;
        }
        
        visited[i][j] = true;
        
        dfs(heights, visited, heights[i][j], i + 1, j);
        dfs(heights, visited, heights[i][j], i - 1, j);
        dfs(heights, visited, heights[i][j], i, j + 1);
        dfs(heights, visited, heights[i][j], i, j - 1);
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 417 (Pacific Atlantic Water Flow)?

This page provides optimized solutions for LeetCode problem 417 (Pacific Atlantic Water Flow) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 417 (Pacific Atlantic Water Flow)?

The time complexity for LeetCode 417 (Pacific Atlantic Water Flow) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 417 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 417 in Java, C++, or Python.

Back to LeetCode Solutions