Solution: Pacific Atlantic Water Flow

Blind 75

Problem Statement:

You are given a matrix grid of size m x n, where each matrix[i][j] represents the height of the Island at ith row and jth column position from the sea level. The Pacific Ocean touches the island's left and top edges, and the Atlantic Ocean touches the island's right and bottom edges.

Due to heavy rain, there is a lot of water on each cell of the island. It is given that the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell's height is less than or equal to the current cell's height. Water can flow from any cell adjacent to an ocean into the ocean.

Return a 2D list result, where result[i] = [ri, ci] represents that rainwater can flow from cell (ri, ci) to both the Pacific and Atlantic oceans.

Example 1:

Input: matrix =

[[1,2,2,3],
 [3,2,3,4],
 [2,4,5,3],
 [5,7,1,4]]

Expected Output: [[0, 3], [1, 3], [2, 2], [3, 0], [3, 1]]

Justification: The cells that can flow to both the Pacific and Atlantic oceans are [[0, 3], [1, 3], [2, 2], [3, 0], [3, 1]]
- [0,3]:
  - [0, 3] -> Pacific Ocean.
  - [0, 3] -> Atlantic Ocean.
- [1,3]:
  - [1, 3] -> [0, 3] -> Pacific Ocean.
  - [1, 3] -> Atlantic Ocean.
- [2, 2]:
  - [2, 2] -> [1, 2] -> [0, 2] -> Pacific Ocean.
  - [2, 2] -> [2, 3] -> Atlantic Ocean.
- [3,0]:
  - [3, 0] -> Pacific Ocean.
  - [3, 0] -> Atlantic Ocean.
- [3,1]:
  - [3, 1] -> [3, 0] -> Pacific Ocean.
  - [3, 1] -> Atlantic Ocean.

Example 2:

Input: matrix =

[[1,2,3],
 [4,5,6],
 [7,8,9]]

Expected Output: [[0,2],[1,2],[2,0],[2,1],[2,2]]

Justification: The cells that can flow to both the Pacific and Atlantic oceans are
- [0,2]:
  - [0, 2] -> Pacific Ocean.
  - [0, 2] -> Atlantic Ocean.
- [1,2]:
  - [1,2] -> [0,2] -> Pacific Ocean.
  - [1,2] -> Atlantic Ocean.
- [2,0]:
  - [2, 0] -> Pacific Ocean.
  - [2, 0] -> Atlantic Ocean.
- [2,1]:
  - [2,1] -> [1,1] -> [1, 0] -> Pacific Ocean.
  - [2,1] -> Atlantic Ocean.
- [2,2]:
  - [2, 2] -> Pacific Ocean.
  - [2, 2] -> Atlantic Ocean.

Example 3:

Input: matrix =

[[10,10,10],
 [10,1,10],
 [10,10,10]]

Expected Output: [[0,0],[0,1],[0,2],[1,0],[1,2],[2,0],[2,1],[2,2]]

Justification: The water can flow to both oceans from all cells except from the central cell [1,1].

Constraints:

m == matrix.length
n == matrix[r].length
1 <= m, n <= 200
0 <= matrix[r][c] <= 105

Solution

To solve this problem, we use Depth-First Search (DFS) to determine which cells in the matrix can flow to both the Pacific and Atlantic Oceans. The matrix represents a grid where each cell's value indicates its height. Water can flow from a cell to its neighboring cells (north, south, east, west) only if the neighboring cell's height is less than or equal to the current cell's height. We need to identify cells that can flow to both the Pacific and Atlantic Oceans. We initiate DFS from the cells on the borders of the matrix adjacent to each ocean and mark the reachable cells for each ocean.

We use two boolean matrices to keep track of cells that can flow to the Pacific and Atlantic Oceans. Starting from the Pacific-bordering cells (top and left edges) and the Atlantic-bordering cells (bottom and right edges), we perform DFS to mark the reachable cells. Once we have marked the cells that can flow to each ocean, we iterate through the matrix to find cells that can flow to both oceans (cells that are marked in both boolean matrices). These cells are our result.

Step-by-Step Algorithm

Initialization:
- Check if the input matrix is empty. If it is, return an empty list.
- Initialize two boolean matrices, pacific and atlantic, to track cells that can reach each ocean.
DFS Initialization:
- Perform DFS from all cells in the first row and first column to mark cells reachable by the Pacific Ocean.
- Perform DFS from all cells in the last row and last column to mark cells reachable by the Atlantic Ocean.
DFS Implementation:
- Implement the DFS function to mark cells in the boolean matrices. The DFS function takes the current cell's coordinates, the boolean matrix to mark, and the height constraint (the height of the previous cell).
- In the DFS function, check if the current cell is within bounds, has not been visited, and meets the height constraint.
- Mark the current cell as visited.
- Recursively perform DFS for all neighboring cells (north, south, east, west).
Collect Results:
- Iterate through all cells in the matrix.
- Collect the coordinates of cells that can reach both the Pacific and Atlantic Oceans.
Return Results:
- Return the list of coordinates where water can flow to both oceans.

Algorithm Walkthrough

Input:

[[1, 2, 2, 3],
 [3, 2, 3, 4],
 [2, 4, 5, 3],
 [5, 7, 1, 4]]

DFS for Pacific Ocean

From the top-left corner (0,0):
- Start DFS from (0,0):
 - Mark (0,0) as reachable in pacific.
 - Right to (0,1) (2 ≥ 1):
 - Mark (0,1) as reachable.
 - Right to (0,2) (2 ≥ 2):
 - Mark (0,2) as reachable.
 - Right to (0,3) (3 ≥ 2):
 
 Mark (0,3) as reachable.
 
 Right to (0,4) (out of bounds, stop DFS).
 
 Down to (1,3) (4 ≥ 3):
 
 Mark (1,3) as reachable.
 
 Right to (1,4) (out of bounds, stop DFS).
 
 Down to (2,3) (3 < 4, stop DFS).
 
 Left to (1,2) (3 < 4, stop DFS).
 
 Up to (0,3) (already visited).
 
 Left to (0,2) (already visited).
 
 Up to (-1,3) (out of bounds, stop DFS).
 - Left to (0,1) (already visited).
 - Down to (1,2) (3 ≥ 2):
 
 Mark (1,2) as reachable.
 
 Right to (1,3) (already visited).
 
 Down to (2,2) (5 ≥ 3):
 
 Mark (2,2) as reachable.
 
 Right to (2,3) (3 < 5, stop DFS).
 
 Down to (3,2) (1 < 5, stop DFS).
 
 Left to (2,1) (4 < 5, stop DFS).
 
 Up to (1,2) (already visited).
 
 Left to (1,1) (2 < 3, stop DFS).
 
 Up to (0,2) (already visited).
 - Left to (0,0) (already visited).
 - Down to (1,1) (mark visited).
 
 Only move in the down direction and visit 4 and 7.
 
 Also, visit 3 at (1, 0) by moving left form (1, 1).
 - Up to (-1,1) (out of bounds, stop DFS).
 - Left to (0,0) (already visited).
- Down to (1,0) (3 ≥ 2):
 - Mark (1,0) as reachable.
 - Right to (1,1) (2 < 3, stop DFS).
 - Down to (2,0) (2 < 3, stop DFS).
 - Left to (1,-1) (out of bounds, stop DFS).
 - Up to (0,0) (already visited).
- Stop DFS.
- Final pacific matrix after processing (0,0):
```
[[true, true, true, true],
 [true, true, true, true],
 [false, true, true, false],
 [false, true, false, false]]
```
From the left column:
- Start DFS from (2,0):
  - Mark (2,0) as reachable.
  - Right to (2,1) (already visited):
  - Down to (3,0) (5 ≥ 2):
    - Mark (3,0) as reachable.
    - Right to (3,1) (already visited).
    - Down to (4,0) (out of bounds, stop DFS).
    - Left to (3,-1) (out of bounds, stop DFS).
    - Up to (2,0) (already visited).
- Final pacific matrix after processing (2,0):
```
[[true, true, true, true],
 [true, true, true, true],
 [true, true, true, false],
 [true, true, false, false]]
```

DFS for Atlantic Ocean

From the bottom row:
- Start DFS from (3,0):
 - Mark (3,0) as reachable in atlantic.
 - Right to (3,1) (7 ≥ 5):
 - Mark (3,1) as reachable.
 - Right to (3,2) (1 < 7, stop DFS).
 - Down to (4,1) (out of bounds, stop DFS).
 - Left to (3,0) (already visited).
 - Up to (2,1) (4 < 7, stop DFS).
 - Down to (4,0) (out of bounds, stop DFS).
 - Left to (3,-1) (out of bounds, stop DFS).
 - Up to (2,0) (2 < 5, stop DFS).
- Final atlantic matrix after processing (3,0):
```
[[false, false, false, false],
 [false, false, false, false],
 [false, false, false, false],
 [true, true, false, false]]
```
- (3,1) is already visited. So, skip it.
- Start DFS from (3,2):
 - Mark (3,2) as reachable in atlantic.
 - Right to (3,3) (4 ≥ 1):
 - Mark (3,3) as reachable.
 - We can't move to any other node from (3, 3).
 - Down to (4,3) (out of bounds, stop DFS).
 - Left to (3,1) (Already visited).
 - Up to (2,2) (5 > 1):
 - Mark (2,2) as reachable.
 - We can't move to any other node from (3, 3).
- Final atlantic matrix after processing (3,0):
```
[[false, false, false, false],
 [false, false, false, false],
 [false, false, true, false],
 [true, true, true, true]]
```
- (3,3) is already visited. So, skip it.
From the right column:
- Start DFS from (0,3):
  - Mark (3,3) as reachable in atlantic.
    - We can move in the down direction to (1, 3).
      - We can't move to any other node from (1, 3).
- Start DFS from (2,3):
  - Mark (2,3) as reachable in atlantic.
    - We can move to any other node from (2, 3).
  Final atlantic matrix after processing (2,3):
```
[[false, false, false, true],
 [false, false, false, true],
 [false, false, true, true],
 [true, true, true, true]]
```

Collect Results

Iterate through the matrix to find cells that are marked in both pacific and atlantic:
- (0,3): pacific[0][3] and atlantic[0][3] are true.
- (1,3): pacific[1][3] and atlantic[1][3] are true.
- (2,2): pacific[2][2] and atlantic[2][2] are true.
- (3,0): pacific[3][0] and atlantic[3][0] are true.
- (3,1): pacific[3][1] and atlantic[3][1] are true.

Return Results

The result is [[0,3], [1,3], [2,2], [3,0], [3,1]].

Final State of Matrices

Pacific Matrix:

   [[true, true, true, true],
    [true, true, true, true],
    [true, true, true, false],
    [true, true, false, false]]

Atlantic Matrix:

   [[false, false, false, true],
    [false, false, false, true],
    [false, false, true, true],
    [true, true, true, true]]

Code

Python3

Complexity Analysis

Time Complexity: $O(m \times n)$ where m is the number of rows and n is the number of columns in the matrix. This is because each cell is visited once for both oceans.

Space Complexity: $O(m \times n)$ due to the two additional matrices (for Pacific and Atlantic) to keep track of visited cells.