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 that can flow to both the Pacific and Atlantic oceans. Return a list of coordinates [row, col] of these cells.

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 the borders touching the Pacific (first row and first column) in pacific to true, and the borders touching the Atlantic (last row and last column) in atlantic to true.

2. Depth-First Search (DFS): Perform a DFS starting from each cell on the Pacific and Atlantic borders. During the DFS, mark cells reachable from the respective ocean as true in the corresponding boolean matrix.

3. Find Common Cells: Iterate through the pacific and atlantic matrices. If a cell is marked as true in both matrices, it means water can flow to both oceans. Add its coordinates to the result list.

4. Return Result: Return the list of coordinates.

Explanation

The DFS explores all reachable cells from a starting point. It ensures that water can flow from a given cell to the ocean because the DFS only proceeds to cells with heights not greater than the current cell. By performing DFS from all border cells, we comprehensively identify all cells connected to the Pacific or Atlantic. Finally, comparing both boolean matrices identifies cells connected to both.

Code

#include <vector>

using namespace std;

class Solution {
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        int m = heights.size();
        int n = heights[0].size();
        vector<vector<bool>> pacific(m, vector<bool>(n, false));
        vector<vector<bool>> atlantic(m, vector<bool>(n, false));
        vector<vector<int>> result;

        // Initialize border cells
        for (int i = 0; i < m; ++i) {
            pacific[i][0] = true;
            atlantic[i][n - 1] = true;
        }
        for (int j = 0; j < n; ++j) {
            pacific[0][j] = true;
            atlantic[m - 1][j] = true;
        }

        // DFS for Pacific
        for (int i = 0; i < m; ++i) {
            dfs(heights, pacific, i, 0);
            dfs(heights, pacific, i, n - 1);
        }
        for (int j = 0; j < n; ++j) {
            dfs(heights, pacific, 0, j);
            dfs(heights, pacific, m - 1, j);
        }

        // DFS for Atlantic
        for (int i = 0; i < m; ++i) {
            dfs(heights, atlantic, i, 0);
            dfs(heights, atlantic, i, n - 1);
        }
        for (int j = 0; j < n; ++j) {
            dfs(heights, atlantic, 0, j);
            dfs(heights, atlantic, m - 1, j);
        }


        // Find common cells
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (pacific[i][j] && atlantic[i][j]) {
                    result.push_back({i, j});
                }
            }
        }

        return result;
    }

private:
    void dfs(const vector<vector<int>>& heights, vector<vector<bool>>& ocean, int row, int col) {
        int m = heights.size();
        int n = heights[0].size();
        if (row < 0 || row >= m || col < 0 || col >= n || ocean[row][col]) return;
        ocean[row][col] = true;
        int height = heights[row][col];
        int dr[] = {-1, 1, 0, 0};
        int dc[] = {0, 0, -1, 1};
        for (int i = 0; i < 4; ++i) {
            int newRow = row + dr[i];
            int newCol = col + dc[i];
            if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && heights[newRow][newCol] <= height) {
                dfs(heights, ocean, newRow, newCol);
            }
        }
    }
};

Complexity

• Time Complexity: O(M*N), where M and N are the dimensions of the input matrix. This is because we visit each cell at most once during the DFS.

• Space Complexity: O(M*N), mainly due to the boolean matrices pacific and atlantic used to track reachable cells. The call stack for the recursive DFS also contributes but is at most O(M+N) in the worst case.