Pacific Atlantic Water Flow - Leetcode Solution

Problem:

You are given a 2D matrix representing the heights of mountains. The matrix has rows and columns are numbered from 0 to N-1. The Pacific ocean touches the top/left border and the Atlantic ocean touches the bottom/right border.

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

Note:

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

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]]

Explanation:

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

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

The list of grid coordinates that water can flow to both the Pacific and Atlantic ocean is: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]].

Solution:

The problem can be solved using a depth-first search (DFS) algorithm. We will start the search from each point on the border of the matrix. For example, we will start from points (0,0), (1,0), (2,0),..., (n-1,0) and (0,0), (0,1),..., (0,m-1) to check if water can flow to the Pacific ocean. We do the same for points on the border of the matrix that touch the Atlantic ocean.

For each starting point, we will keep a boolean matrix to mark the cells that can be reached by water from that point. We will perform a DFS starting from that point and mark the cells that can be reached by water. We will repeat this process for every starting point. Finally, we will find the coordinates where the same cell has been marked by both matrices and add them to the result.

Here is the Python code implementation:

class Solution: def init(self): self.directions = [(1,0),(-1,0),(0,1),(0,-1)] self.m = 0 self.n = 0 self.heights = [] self.visited_pacific = [] self.visited_atlantic = []

def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
    if not heights:
        return []
    self.m = len(heights)
    self.n = len(heights[0])
    self.heights = heights
    self.visited_pacific = [[False]*self.n for _ in range(self.m)]
    self.visited_atlantic = [[False]*self.n for _ in range(self.m)]
    for i in range(self.m):
        self._dfs(i, 0, self.visited_pacific)
        self._dfs(i, self.n-1, self.visited_atlantic)
    for i in range(self.n):
        self._dfs(0, i, self.visited_pacific)
        self._dfs(self.m-1, i, self.visited_atlantic)
    res = []
    for i in range(self.m):
        for j in range(self.n):
            if self.visited_pacific[i][j] and self.visited_atlantic[i][j]:
                res.append([i, j])
    return res

def _dfs(self, x, y, visited):
    visited[x][y] = True
    for dx, dy in self.directions:
        nx, ny = x + dx, y + dy
        if nx < 0 or nx >= self.m or ny < 0 or ny >= self.n:
            continue
        if visited[nx][ny] or self.heights[nx][ny] < self.heights[x][y]:
            continue
        self._dfs(nx, ny, visited)

1