Pacific Atlantic Water Flow

To solve this problem, we need to find the cells from which water can flow to both the Pacific and Atlantic oceans. We will perform two Depth-First Search (DFS) traversals: one starting from the cells touching the Pacific Ocean (top and left edges) and the other starting from the cells touching the Atlantic Ocean (right and bottom edges).

Here’s the step-by-step process:

  1. Create two boolean matrices pacific and atlantic of size m x n to keep track of the cells that can reach the Pacific and Atlantic oceans respectively.
  2. Run a DFS from the top and left edges to fill the pacific matrix, marking the reachable cells as True.
  3. Run a DFS from the right and bottom edges to fill the atlantic matrix, marking the reachable cells as True.
  4. Iterate through both matrices to find the cells that can reach both oceans (cells with True in both matrices) and return their coordinates.

Below is the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        if not heights:
            return []

        m, n = len(heights), len(heights[0])
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        pacific = [[False] * n for _ in range(m)]
        atlantic = [[False] * n for _ in range(m)]

        def dfs(x, y, visited):
            visited[x][y] = True
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny] and heights[nx][ny] >= heights[x][y]:
                    dfs(nx, ny, visited)

        # DFS from Pacific
        for i in range(m):
            dfs(i, 0, pacific)
        for j in range(n):
            dfs(0, j, pacific)

        # DFS from Atlantic
        for i in range(m):
            dfs(i, n - 1, atlantic)
        for j in range(n):
            dfs(m - 1, j, atlantic)

        # Find common cells
        result = [[i, j] for i in range(m) for j in range(n) if pacific[i][j] and atlantic[i][j]]
        return result

This code will return the required 2D list of grid coordinates where water can flow to both the Pacific and Atlantic oceans, as per the given problem statement.

Define the Interface Input: matrix (coordinates consisting of integer) Output: grid of coordinates

Identify the Invariants

  • mxn
  • position of the pacific and atlantic ocean

Identify the constraints

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

Search the Problem Space

  • grid

Classify the Problem

  • Grid Traversal

Analyze the Examples We can represent the flow of water as a graph with nodes representing the unit cell Rules for the flow of water can be applied to each cell to figure out the directionality of the edges Edges can be unidirectional or bidirectional

Converting the grid coordinates to a graph consisting of nodes Figure out the directionality of the edges Apply the rules for the water flow We have to check each node in the graph, whether it has a path to P and A. If it does, then we need to add the coordinate to the result array of array

Do we need a graph data structure to solve this problem?

Solve the Problem by Hand We created the graph We represented the co-ordinates on the diagram Overlay the coordinates and check the path exists or not

Describe the Pattern

  • We don’t care whether it is shortest/longest path
  • If it has at least one path to P and A
  • The first row and first column is connected to P
  • The last row and last column is connected to A
  • Any nodes that is not in the first row, first column last row or last column, we need to check if it can reach any node in the first row or first column (P) AND reach any node in the last row or last column (A)
  • Traverse the grid, we have to check every node

Brute Force Approach

DFS

Base Case

  • If the node is in the first row or first column it can reach P and If the node is in the last row or last column it can reach A
  • The node in the last row and first column can reach A & P
  • The node in the first row and last column can reach A & P.
    • Add the co-ordinates of those nodes to the result

Recursive Cases

  • Non trivial case where we need traverse the graph (one distance away from A) (0, 3) (row, col) (0, n-1) - Check if the node height is greater or equal to the node height in (0, n) We can add that cell also to the result

Do we need to keep track of the nodes visited? We can cache the result of whether it is possible to reach either A or P from that cell.

Out of bounds checking to make sure we are within the grid when traversing right, left, up, down directions = {(0,1), (0, -1), (1,0), (-1, 0)}

Initialize to false for visited[row][col] The dimension of the visited grid will be the same dimension as the original grid (mxnm)

Unit of Work

  • Each node can go up, down, left, right
  • Parent needs to tell which node to process
  • Which nodes have we already visited and can we reach P & A from this node?

Problem Decomposition

  • We can divide the problems into two smaller problems Reach P Reach A We can handle the simpler problems and have a compound condition to check whether a given node can reach both A & P

dfs(matrix, visited, )

Analyze Time and Space Complexity

Outline the Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

def dfs(matrix, i, j, visited)
   visited[i][j] = true
   
  if i+1 < matrix.size && !visited[i+1][j] && matrix[i+1][j] >= matrix[i][j]
    dfs(matrix, i+1, j, visited)   
  end

  if i-1 >= 0 && !visited[i-1][j] && matrix[i-1][j] >= matrix[i][j]
    dfs(matrix, i-1, j, visited)   
  end

  if j+1 < matrix[0].size && !visited[i][j+1] && matrix[i][j+1] >= matrix[i][j]
    dfs(matrix, i, j+1, visited)   
  end

  if j-1 >= 0 && !visited[i][j-1] && matrix[i][j-1] >= matrix[i][j]
    dfs(matrix, i, j-1, visited)   
  end
   
end

# @param {Integer[][]} matrix
# @return {Integer[][]}
def pacific_atlantic(matrix)
    if matrix.empty?
        return []
    end

    pacific = Array.new(matrix.size) do
       Array.new(matrix[0].length, false) 
    end

    atlantic = Array.new(matrix.size) do
       Array.new(matrix[0].length, false) 
    end
#     pacific for left side
    for i in (0...matrix.length)
       dfs(matrix, i, 0, pacific) 
    end
#     upper pacific
    for j in (0...matrix[0].length)
       dfs(matrix, 0, j, pacific) 
    end
#     right side of atlantic
    for i in (0...matrix.length)
       dfs(matrix, i, matrix[0].size-1, atlantic) 
    end
#     bottom atlantic row
    for j in (0...matrix[0].length)
       dfs(matrix, matrix.size - 1, j, atlantic) 
    end

    result = []

    for i in (0...matrix.size)
       for j in (0...matrix[0].size) 
          result << [i, j] if pacific[i][j] && atlantic[i][j]
       end
    end
    result    
end