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:
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).
The description was taken from https://leetcode.com/problems/pacific-atlantic-water-flow/.
#O(M*N) Time, O(M*N) Spaceclass Solution: def pacificAtlantic(self, matrix: List[List[int]]) -> List[List[int]]: if not matrix: return pacific = [[0 for col in range(len(matrix[0]))] for row in range(len(matrix))] atlantic = [[0 for col in range(len(matrix[0]))] for row in range(len(matrix))] output = [] def dfs(row:int, col:int, flow:int, ocean:list) -> None: if row < 0 or col < 0 or row >= len(matrix) or col >= len(matrix[0]): return elif not matrix[row][col] >= flow: return elif ocean[row][col] == 1: return ocean[row][col] = 1 dfs(row - 1, col, matrix[row][col], ocean) dfs(row + 1, col, matrix[row][col], ocean) dfs(row, col - 1, matrix[row][col], ocean) dfs(row, col + 1, matrix[row][col], ocean) for col in range(0,len(matrix[0])): dfs(0,col,float('-inf'),pacific) dfs((len(matrix)-1), col, float('-inf'),atlantic) for row in range(0,len(matrix)): dfs(row,0,float('-inf'),pacific) dfs(row,(len(matrix[0])-1),float('-inf'),atlantic) for row in range(0, len(matrix)): for col in range(0, len(matrix[0])): if pacific[row][col] == 1 and atlantic[row][col] == 1: output.append([row,col]) return outputThis solution is very similar to the Number of Islands problem.
We can solve this by making two matrices, one for the Pacific Ocean and one for the Atlantic.
We will make these for marking which areas water can flow to after a DFS is performed on every part of each ocean's respective cells. This means that we will need a DFS function that we will need to create that will mark cells that water is able to flow to as visited, then we can cross-reference which cells are accessible from both oceans at the end.
Starting off, if the input matrix is empty then we can't get to any part of any ocean, so we will return.
if not matrix: return
Let's initialize our 2D arrays.
These arrays will be used to mark which cells that water can flow to from each respective ocean.
pacific = [[0 for col in range(len(matrix[0]))] for row in range(len(matrix))] atlantic = [[0 for col in range(len(matrix[0]))] for row in range(len(matrix))]The code above basically translates to we will have as many columns as there are in the first row at index zero of the input array, and we will have as many rows as there are in the length of the array, which would be the size of each column.
We will also need our output array that we will append the indices of water that can be flowed to from both oceans.
output = []
Now we will create our recursive, dfs function.
The function will take a row index, a column index, a flow value which is the value of the cell that recursed the function to get to the current cell, and an ocean matrix that the function will mark visited cells within.
def dfs(row:int, col:int, flow:int, ocean:list) -> None:
Before processing a cell, we need to make sure that the cell is valid.
We need to ensure that the cell is within the bounds of the input matrix, if not, then we will return.
if row < 0 or col < 0 or row >= len(matrix) or col >= len(matrix[0]): return
Also, according to the description, water can only flow from a cell to another one with a height that is equal or lower.
From that, we would probably expect that we would have to check that the current cell is less than or equal to the input flow.
However, that is what the case is when the water flows outward, we are stimulating the opposite effect by calling a DFS on the outer edges of the matrix and coming inward.
It is because of this that we will want to only process the current cell if its flow is greater than or equal to the previous flow.
If that isn't the case, we will return.
elif not matrix[row][col] >= flow: return
If we imagine watching the water from the problem flowing outward into the Pacific and Atlantic, then imagine playing the video in reverse, that is basically what we are doing here.
Also, if the current cell for whichever ocean matrix we are currently about to mark is already a one, then we have already processed this path and will return from here.
elif ocean[row][col] == 1: return
If none of the previous cases are true, we have flowed to a valid cell of water so we will mark it as visited then call the DFS function on each surrounding cell.
ocean[row][col] = 1 dfs(row - 1, col, matrix[row][col], ocean) dfs(row + 1, col, matrix[row][col], ocean) dfs(row, col - 1, matrix[row][col], ocean) dfs(row, col + 1, matrix[row][col], ocean)
Now we will call the DFS function on the values closest to the top, Pacific, and bottom, Atlantic oceans.
| 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 |
for col in range(0,len(matrix[0])): dfs(0,col,float('-inf'),pacific) dfs((len(matrix)-1), col, float('-inf'),atlantic) print(col)
Then, we will call the DFS function on the values closest to the left, Pacific, and right, Atlantic oceans.
| 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 |
for row in range(0,len(matrix)): dfs(row,0,float('-inf'),pacific) dfs(row,(len(matrix[0])-1),float('-inf'),atlantic)
Lastly, we will iterate over both ocean arrays and see which cells have been visited in both arrays, append them to the output then return the output.
| 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 |
| 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 |
| 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 |
for row in range(0, len(matrix)): for col in range(0, len(matrix[0])): if pacific[row][col] == 1 and atlantic[row][col] == 1: output.append([row,col]) return output