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 cell is less than or equal to the height of the adjacent cell.

Find the cells from which water can flow to both the Pacific and Atlantic oceans. Return a list of coordinates where the coordinates are represented as [row, col]. 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 the border cells touching the Pacific (first row and first column) in pacific to true, and similarly, initialize the border cells touching the Atlantic (last row and last column) in atlantic to true.

2. Depth-First Search (DFS): Perform a depth-first search from each cell marked true in pacific and atlantic. During the DFS:

   • Explore adjacent cells.
   • If an adjacent cell has a height greater than or equal to the current cell's height, and it hasn't been visited (marked as true), mark it as visited (set to true) and recursively call DFS on it.

3. Find Common Cells: Iterate through the pacific and atlantic matrices. If a cell is 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 approach systematically explores all reachable cells from the ocean boundaries. By marking visited cells, we avoid infinite loops. The final step identifies cells reachable from both oceans. The condition heights[row][col] <= heights[newRow][newCol] ensures that water flows downhill (or on a level surface).

Code

using System;
using System.Collections.Generic;

public class Solution {
    public IList<IList<int>> PacificAtlantic(int[][] heights) {
        int m = heights.Length;
        int n = heights[0].Length;
        bool[,] pacific = new bool[m, n];
        bool[,] atlantic = new bool[m, n];
        IList<IList<int>> result = new List<IList<int>>();

        // 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++) {
            for (int j = 0; j < n; j++) {
                if (pacific[i, j]) DFS(heights, pacific, i, j);
            }
        }

        // DFS for Atlantic
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (atlantic[i, j]) DFS(heights, atlantic, i, 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.Add(new List<int> { i, j });
                }
            }
        }

        return result;
    }

    private void DFS(int[][] heights, bool[,] ocean, int row, int col) {
        int m = heights.Length;
        int n = heights[0].Length;
        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 &&
                !ocean[newRow, newCol] && heights[newRow][newCol] <= height) {
                ocean[newRow, newCol] = true;
                DFS(heights, ocean, newRow, newCol);
            }
        }
    }
}

Complexity

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

• Space Complexity: O(M * N) due to the pacific and atlantic boolean matrices, and the recursion stack during the DFS. In the worst case, the recursion stack could have a depth of M * N.