Pacific Atlantic Waterflow

 In this solution, the aim is to find cells that can flow water to both the Pacific Ocean and the Atlantic Ocean.

The problem considers a height map where water can only flow from a cell to a neighboring cell with a non-negative height difference (i.e., water flows from higher to lower ground).

We are simply identifying cells that can drain water to both the Pacific Ocean (left and top borders) and the Atlantic Ocean (right and bottom borders).

Solution

The solution to the Pacific Atlantic water flow problem involves simulating the water flow from the edges of the grid towards the inner cells using Depth-First Search (DFS). The primary thought process can be broken down as follows:

Grid Definition

•         We have a grid of heights where each cell contains the height of the terrain at that point.
•         Water can flow from a cell to its adjacent cells (up, down, left, right) if the adjacent cell has an equal or lower height.

Pacific and Atlantic Oceans

•         Water can flow into the Pacific Ocean if it starts from any cell on the left or top edges of the grid.
•         Water can flow into the Atlantic Ocean if it starts from any cell on the right or bottom edges of the grid.

The goal is to Identify all cells from which water can flow to both the Pacific and Atlantic Oceans.

class Solution:

    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        """
        Finds all cells that can flow water to both the Pacific Ocean and the Atlantic Ocean.

        Args:
            heights (List[List[int]]): A 2D list representing the height map, where heights[r][c] represents the height
                                       of cell (row r, column c).

        Returns:
            List[List[int]]: A list of lists containing the coordinates (row, column) of cells that can flow water
                             to both the Pacific and Atlantic Oceans.
        """
        if not heights:
            return []

        num_rows, num_cols = len(heights), len(heights[0])
        pacific_reachable = set()  # Cells reachable from the Pacific Ocean
        atlantic_reachable = set()  # Cells reachable from the Atlantic Ocean

        def dfs(row, col, visited, prev_height):
            """
            Performs a Depth-First Search (DFS) traversal to explore reachable cells from a given starting point.

            Args:
                row (int): The row index of the current cell.
                col (int): The column index of the current cell.
                visited (set): A set of visited cells to avoid revisiting.
                prev_height (int): The height of the previous cell to ensure water can flow downwards.
            """

            if (row, col) in visited or \
               row < 0 or col < 0 or row >= num_rows or col >= num_cols or \
               heights[row][col] < prev_height:
                return

            visited.add((row, col))
            dfs(row + 1, col, visited, heights[row][col])  # Explore down
            dfs(row - 1, col, visited, heights[row][col])  # Explore up
            dfs(row, col + 1, visited, heights[row][col])  # Explore right
            dfs(row, col - 1, visited, heights[row][col])  # Explore left

        # Start DFS from all cells on the borders (Pacific and Atlantic)
        for col in range(num_cols):
            dfs(0, col, pacific_reachable, heights[0][col])  # Pacific Ocean (top border)
            dfs(num_rows - 1, col, atlantic_reachable, heights[num_rows - 1][col])  # Atlantic Ocean (bottom border)

        for row in range(num_rows):
            dfs(row, 0, pacific_reachable, heights[row][0])  # Pacific Ocean (left border)
            dfs(row, num_cols - 1, atlantic_reachable, heights[row][num_cols - 1])  # Atlantic Ocean (right border)

        # Find cells reachable from both oceans
        result = []
        for row in range(num_rows):
            for col in range(num_cols):
                if (row, col) in pacific_reachable and (row, col) in atlantic_reachable:
                    result.append([row, col])

        return result

Strategy to the Solution

Initialization

•         Use two sets to keep track of cells that can reach the Pacific and Atlantic Oceans (pacific_reachable and atlantic_reachable).

DFS for Water Flow Simulation

•         Use DFS to simulate water flowing from the ocean edges into the grid.
•         Start the DFS from all cells on the Pacific border (left and top edges) and mark all reachable cells in pacific_reachable.
•         Similarly, start the DFS from all cells on the Atlantic border (right and bottom edges) and mark all reachable cells in atlantic_reachable.

Combining Results

•         Cells that are present in both pacific_reachable and atlantic_reachable are the cells from which water can flow to both oceans.
•         Return these cells as the result.

Time Complexity

The time complexity is determined by the number of cells in the grid and the operations performed on each cell.

DFS Traversal

•         Each cell in the grid can be visited multiple times: once for the DFS starting from the Pacific Ocean border and once for the DFS starting from the Atlantic Ocean border.
•         In the worst case, each DFS might visit all cells in the grid.
•         Therefore, the time complexity of the DFS part is O(m multiplied by n) for the Pacific Ocean and O(m multiplied by n) for the Atlantic Ocean, where m is the number of rows and n is the number of columns.

Overall DFS

•         Since we perform two separate DFS traversals (one for each ocean), the total time complexity is 2 (m multiplied by n)=O(m multiplied by n).

Space Complexity

The space complexity is influenced by the space required for storing visited cells and the call stack for DFS.

Visited Sets

•         We maintain two sets (pacific_reachable and atlantic_reachable) to store the cells reachable from each ocean.
•         Each set can store up to m×nm×n cells in the worst case.
•         Thus, the space complexity for the visited sets is 

``` O(m×n) ```

Call Stack for DFS

•         The maximum depth of the DFS call stack is the maximum number of cells that can be traversed in a single DFS call.
•         In the worst case, this depth can be

```m×n```

•         However, the depth of the DFS stack is typically limited by the number of rows or columns, giving a space complexity of

for the call stack.

Unit tests

Here are sample test cases to establish the accuracy and robustness of this solution.

import unittest
from typing import List

class TestPacificAtlantic(unittest.TestCase):

    def setUp(self):
        self.solution = Solution()
        
    def test_example_case(self):
        # Example height map
        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]
        ]

        expected_result = [[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]]
        actual_result = self.solution.pacificAtlantic(heights)

        self.assertEqual(sorted(actual_result), sorted(expected_result))

    def test_empty_heights(self):
        # Test with an empty height map
        heights = []

        actual_result = self.solution.pacificAtlantic(heights)

        self.assertEqual(actual_result, [])

    # Add more test cases as needed

if __name__ == "__main__":
    unittest.main()