Pacific Atlantic Water flow

XXX. Pacific Atlantic Water Flow

Breadth-First Search

Depth-First Search

Matrix

Problem Statement:

Given an m x n matrix representing the height of each cell, find all cells that can flow water to both the Pacific and Atlantic oceans.

Water can flow from a cell to another one directly north, south, east, or west if the elevation of the destination cell is less than or equal to the elevation of the current cell.

Algorithm:

1. Initialize two boolean matrices pacific and atlantic to track the cells that can flow to each ocean.
2. Perform a BFS or DFS starting from the cells adjacent to the Pacific Ocean (top row and left column).
3. Repeat the BFS/DFS for the cells adjacent to the Atlantic Ocean (bottom row and right column).
4. For each cell in the matrix, check if it is reachable from both oceans. If so, add it to the result list.

Complexity:

Time Complexity: O(m * n), where m and n are the dimensions of the matrix.
Space Complexity: O(m * n) for the visited matrices and the BFS/DFS stack or queue.

Java Implementation:

public class Solution {
    public List pacificAtlantic(int[][] matrix) {
        if (matrix.length == 0) return new ArrayList<>();
        int m = matrix.length, n = matrix[0].length;
        List result = new ArrayList<>();
        boolean[][] pacific = new boolean[m][n];
        boolean[][] atlantic = new boolean[m][n];

        for (int j = 0; j < n; j++) {
            bfs(pacific, matrix, new Tuple(0, j));
            bfs(atlantic, matrix, new Tuple(m - 1, j));
        }
        for (int i = 0; i < m; i++) {
            bfs(pacific, matrix, new Tuple(i, 0));
            bfs(atlantic, matrix, new Tuple(i, n - 1));
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pacific[i][j] && atlantic[i][j]) result.add(new int[]{i, j});
            }
        }
        return result;
    }

    private void bfs(boolean[][] ocean, int[][] matrix, Tuple start) {
        Queue queue = new LinkedList<>();
        queue.add(start);
        int m = matrix.length, n = matrix[0].length;
        while (!queue.isEmpty()) {
            Tuple curr = queue.poll();
            ocean[curr.x][curr.y] = true;
            int[] dx = {0, 1, 0, -1};
            int[] dy = {1, 0, -1, 0};
            for (int i = 0; i < dx.length; i++) {
                int newX = curr.x + dx[i];
                int newY = curr.y + dy[i];
                if (newX >= 0 && newY >= 0 && newX < m && newY < n && !ocean[newX][newY] && matrix[newX][newY] >= matrix[curr.x][curr.y]) {
                    queue.add(new Tuple(newX, newY));
                }
            }
        }
    }

    class Tuple {
        int x, y;
        public Tuple(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}
                

Python Implementation:

from collections import deque

def pacificAtlantic(matrix):
    if not matrix:
        return []
    m, n = len(matrix), len(matrix[0])
    pacific = [[False] * n for _ in range(m)]
    atlantic = [[False] * n for _ in range(m)]

    def bfs(ocean, start_points):
        queue = deque(start_points)
        while queue:
            x, y = queue.popleft()
            ocean[x][y] = True
            for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
                newX, newY = x + dx, y + dy
                if 0 <= newX < m and 0 <= newY < n and not ocean[newX][newY] and matrix[newX][newY] >= matrix[x][y]:
                    queue.append((newX, newY))

    bfs(pacific, [(0, j) for j in range(n)] + [(i, 0) for i in range(m)])
    bfs(atlantic, [(m - 1, j) for j in range(n)] + [(i, n - 1) for i in range(m)])

    result = []
    for i in range(m):
        for j in range(n):
            if pacific[i][j] and atlantic[i][j]:
                result.append([i, j])
    return result