Pacific Atlantic Water Flow medium

Problem Statement

You are given an m x n integer matrix heights representing the height of each unit cell in a continent. The Pacific ocean touches the left and top edges of the continent, and the Atlantic ocean touches the right and bottom edges.

Water can only flow in four directions: up, down, left, and right. Water flows from a cell to an adjacent cell only if the height of the adjacent cell is not higher than the height of the current cell.

Find the cells from which water can flow to both the Pacific and Atlantic oceans. Return a list of coordinates of these cells. You may return the answer in any order.

Example 1

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

Steps

1. Initialization: Create two boolean matrices, pacific and atlantic, of the same size as heights. Initialize pacific to true for cells touching the Pacific (first row and first column), and atlantic to true for cells touching the Atlantic (last row and last column).
2. Depth-First Search (DFS): Perform DFS for both pacific and atlantic. The DFS function explores adjacent cells, marking them as reachable if the height is not higher than the current cell and the cell hasn't been visited.
3. Finding Common Cells: Iterate through the matrices and find cells where both pacific[i][j] and atlantic[i][j] are true. These are the cells reachable from both oceans.
4. Return Result: Return the coordinates of these cells.

Explanation

The solution uses Depth-First Search (DFS) to explore which cells can reach the Pacific and Atlantic oceans. The DFS recursively explores adjacent cells, only moving to cells with heights less than or equal to the current cell. By running DFS from both the Pacific and Atlantic edges, we identify cells reachable from both. The final step involves collecting these cells' coordinates.

Code

import java.util.ArrayList;
import java.util.List;

class Solution {
    private int rows, cols;

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        rows = heights.length;
        cols = heights[0].length;
        boolean[][] pacific = new boolean[rows][cols];
        boolean[][] atlantic = new boolean[rows][cols];
        List<List<Integer>> result = new ArrayList<>();

        // Initialize Pacific and Atlantic boundaries
        for (int i = 0; i < rows; i++) {
            dfs(heights, pacific, i, 0);
            dfs(heights, atlantic, i, cols - 1);
        }
        for (int j = 0; j < cols; j++) {
            dfs(heights, pacific, 0, j);
            dfs(heights, atlantic, rows - 1, j);
        }

        // Find common cells
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (pacific[i][j] && atlantic[i][j]) {
                    List<Integer> cell = new ArrayList<>();
                    cell.add(i);
                    cell.add(j);
                    result.add(cell);
                }
            }
        }
        return result;
    }

    private void dfs(int[][] heights, boolean[][] ocean, int row, int col) {
        if (row < 0 || row >= rows || col < 0 || col >= cols || ocean[row][col]) return;
        ocean[row][col] = true;
        int height = heights[row][col];
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // Right, Left, Down, Up
        for (int[] dir : directions) {
            int newRow = row + dir[0];
            int newCol = col + dir[1];
            if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && heights[newRow][newCol] <= height) {
                dfs(heights, ocean, newRow, newCol);
            }
        }
    }
}

Complexity

• Time Complexity: O(M*N), where M and N are the dimensions of the matrix. We visit each cell at most once during the DFS.
• Space Complexity: O(MN) due to the pacific and atlantic boolean matrices, plus the space used by the recursion stack during DFS, which in the worst case could be O(MN). The result list also contributes to space complexity, but it's bounded by the number of cells in the matrix.