[LeetCode] Pacific Atlantic Water Flow

Problem: Given an m x n matrix of non-negative integers representing the height of each unit cell in a continent, the "Pacific ocean" touches the left and top edges of the matrix and the "Atlantic ocean" touches the right and bottom edges.

Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.

Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.

Note:

1. The order of returned grid coordinates does not matter.
2. Both m and n are less than 150.

Example:

Given the following 5x5 matrix:

  Pacific ~   ~   ~   ~   ~ 
       ~  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  *
          *   *   *   *   * Atlantic

Return:

[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).

Approach: Let's just solve a subproblem first, what if only one ocean was given. How would we have solved this question then. If you see the water can flow from one cell to another connected cell if the height of the next cell is less than the current cell. If you look closely, its a graph where one node node1(i, j) is connected to another node node2(k, l) if matrix[i][j] <= matrix[k][l] and k = i + 1 or k = i - 1 and j = l or k = i and l = j + 1 or l = j - 1.

Once we build the graph, we can apply DFS to see whether there is a path exist from cell (i, j) to (0, 0) or not. If yes then we can say that from (i, j) water can flow to pacific.

Now given that we have two oceans here. What we can do is we can maintain two 2D Boolean tables of size m x n to say pacific and atlantic. pacific[i][j] will be true only if there is a path exist from (i, j) to (0, 0) that is water can flow to pacific and atlantic[i][j] will be true only if there is a path exist from (i, j) to (m-1, n-1) that is water can flow to atlantic.

In the end we can just return the all the cells (i, j) where pacific[i][j] and atlantic[i][j] are true.

Implementation in C#:

        public static IList<IList<int>> PacificAtlantic(int[][] matrix)

        {

            List<IList<int>> result = new List<IList<int>>();

            int numRows = matrix.Length;

            if (numRows == 0)

            {

                return result;

            }

            int numCols = matrix[0].Length;

            bool[,] pacific = new bool[numRows, numCols];

            bool[,] atlantic = new bool[numRows, numCols];

            

            // Top and Bottom boundary

            for (int col = 0; col < numCols; ++col)

            {

                PacificAtlanticDFS(matrix, 0, col, matrix[0][col], pacific);

                PacificAtlanticDFS(matrix, numRows - 1, col, matrix[numRows - 1][col], atlantic);

            }

            // Left and right boundary

            for (int row = 0; row < numRows; ++row)

            {

                PacificAtlanticDFS(matrix, row, 0, matrix[row][0], pacific);

                PacificAtlanticDFS(matrix, row, numCols - 1, matrix[row][numCols - 1], atlantic);

            }

            for (int i = 0; i < numRows; ++i)

            {

                for(int j = 0; j < numCols; ++j)

                {

                    if (pacific[i, j] && atlantic[i, j])

                    {

                        List<int> point = new List<int>();

                        point.Add(i);

                        point.Add(j);

                        result.Add(point);

                    }

                }

            }

            return result;

        }

        private static void PacificAtlanticDFS(int[][] matrix, int row, int col, int prevHeight, bool[,] ocean)

        {

            if (row < 0 

                || row >= matrix.Length

                || col < 0

                || col >= matrix[0].Length

                || matrix[row][col] < prevHeight

                || ocean[row, col])

            {

                return;

            }

            ocean[row, col] = true;

            PacificAtlanticDFS(matrix, row + 1, col, matrix[row][col], ocean);

            PacificAtlanticDFS(matrix, row - 1, col, matrix[row][col], ocean);

            PacificAtlanticDFS(matrix, row, col + 1, matrix[row][col], ocean);

            PacificAtlanticDFS(matrix, row, col - 1, matrix[row][col], ocean);

        }

Complexity: O(m*n) where m = number of rows, n = number of columns