Leetcode 417. Pacific Atlantic Water Flow

Problem Explanation:

In this problem, we are given a m x n matrix of non-negative integers where each integer represents the height of each 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 from a cell can flow to another cell in four direction (up, down, left and right), if the height of the cell it is flowing to is less than or equal to the height of the current cell.

Our task is to find the coordinates of the cells where water can flow down to both the Pacific and Atlantic ocean.

For instance, let's take an example of a 5x5 matrix:

1
2
3 Pacific ~~  ~~  ~~  ~~  ~~
4     ~~ 1   2   2   3   (5) *
5     ~~ 3   2   3  (4)  (4) *
6     ~~ 2   4 (5)  3   1   *
7     ~~(6)(7)  1   4   5   *
8     ~~(5)  1  1   2   4   *
9        *   *   *   *   *  Atlantic

In the above matrix, the cells which can flow to both oceans are marked in parentheses. For these cells, water can flow to the cell with an equal or smaller value of height, and reach both the Pacific and Atlantic ocean.

So, the answer for this scenario would be the coordinate of cells marked in parentheses, that is [[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]].

Here, (0,4) is the coordinate of the cell with height 5 from the first row, (1,3) and (1,4) are the coordinates of the cells with height 4 from the second row, and so on.

Solution's Approach:

We can solve this problem using the BFS (Breadth First Search) algorithm. The BFS algorithm starts from a node, explores as far as possible along each branch before backtracking. So, we traverse all nodes in the matrix in two different BFS, one starting from the cells touching the Pacific, and another one starting from the cells touching the Atlantic. For each BFS, we keep track of the visited cells in seperate "seen" matrices.

Finally, the cells where water can flow to both oceans are the ones present in both "seen" matrices. We add those coordinates in our answer.

Please, see the described solution in Python and Java below. The solution is absent in other languages due to the text constraints of the system. The solution approach will remain the same for all languages.

1
2python
3class Solution:
4    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
5        if not heights: return []
6
7        m, n = len(heights), len(heights[0])
8        dirs = [(0,1),(0,-1),(1,0),(-1,0)] #right, left, down, up
9
10        p_visited = [[False for _ in range(n)] for _ in range(m)]
11        a_visited = [[False for _ in range(n)] for _ in range(m)]
12        result = []
13
14        for i in range(m):
15            #vertical border
16            self.dfs(heights, i, 0, p_visited, m, n, dirs)
17            self.dfs(heights, i, n-1, a_visited, m, n, dirs)
18
19        for j in range(n):
20            #horizontal border
21            self.dfs(heights, 0, j, p_visited, m, n, dirs)
22            self.dfs(heights, m-1, j, a_visited, m, n, dirs)
23
24        for i in range(m):
25            for j in range(n):
26                #append cell visited by both searches
27                if p_visited[i][j] and a_visited[i][j]:
28                    result.append([i,j])
29        return result
30
31    def dfs(self, heights, i, j, visited, m, n, dirs):
32        #mark as visited
33        visited[i][j] = True
34        for dir in dirs:
35            x, y = i + dir[0], j + dir[1]
36            if x<0 or y<0 or x>=m or y>=n or visited[x][y] or heights[x][y] < heights[i][j]:
37                #if out of boundary or this cell is higher, we can't flow water from this cell to next cell-> skip
38                continue
39            self.dfs(heights, x, y, visited, m, n, dirs)
40
41solution=Solution()
42print(solution.pacificAtlantic([[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
2java
3import java.util.*;
4public class Main {
5    List<int[]> res = new ArrayList<>();
6    int[] dir = new int[]{1, -1, 0, 0, 0, 0, -1, 1};
7    int m, n;
8    int[][] matrix;
9    public List<int[]> pacificAtlantic(int[][] matrix) {
10        if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
11            return res;
12        }
13        m = matrix.length;
14        n = matrix[0].length;
15        this.matrix = matrix;
16        boolean[][] pVisited = new boolean[m][n];
17        boolean[][] aVisited = new boolean[m][n];
18        Queue<int[]> pQueue = new LinkedList<>();
19        Queue<int[]> aQueue = new LinkedList<>();
20        for(int i=0; i<m; i++){
21            pQueue.offer(new int[]{i, 0});
22            aQueue.offer(new int[]{i, n-1});
23            pVisited[i][0] = true;
24            aVisited[i][n-1] = true;
25        }
26
27        for(int i=0; i<n; i++){
28            pQueue.offer(new int[]{0, i});
29            aQueue.offer(new int[]{m-1, i});
30            pVisited[0][i] = true;
31            aVisited[m-1][i] = true;
32        }
33
34        bfs(pVisited, pQueue);
35        bfs(aVisited, aQueue);
36
37        for(int i=0; i<m; i++){
38            for(int j=0; j<n; j++){
39                if(pVisited[i][j] && aVisited[i][j]){
40                    res.add(new int[]{i, j});
41                }
42            }
43        }
44
45        return res;
46    }
47
48    public void bfs(boolean[][] visited, Queue<int[]> queue){
49        while(!queue.isEmpty()){
50            int[] cur = queue.poll();
51            for(int i=0; i<4; i++){
52                int ni = cur[0] + dir[i], nj = cur[1] + dir[i+4];
53                if(ni >= 0 && ni < m && nj >=0 && nj < n && !visited[ni][nj] && matrix[ni][nj] >= matrix[cur[0]][cur[1]]){
54                    visited[ni][nj] = true;
55                    queue.offer(new int[]{ni, nj});
56                }
57            }
58        }
59    }
60
61    public static void main(String[] args) {
62        Main main = new Main();
63        int[][] matrix = {{1, 2, 2, 3, 5},
64                          {3, 2, 3, 4, 4},
65                          {2, 4, 5, 3, 1},
66                          {6, 7, 1, 4, 5},
67                          {5, 1, 1, 2, 4}};
68        List<int[]> result = main.pacificAtlantic(matrix);
69        for(int[] point : result){
70            System.out.println(Arrays.toString(point));
71        }
72    }
73}

JavaScript Solution:

To solve this problem in JavaScript, we also need to use the BFS algorithm. However, because JavaScript is a prototypal language and lacks some Java specific features like Queue object and because JavaScript treats 2D arrays differently we'll have to alter our approach slightly for JavaScript.

One important thing to take notice is the way 2D arrays are handled. In Javascript creating 2D arrays using the new Array(m).fill(new Array(n).fill(false)) pattern is not advisable because it fills each row with a reference to the same array which effectively makes each row identical. When you modify one row it modifies all the rows. Instead, we have to use the pattern new Array(m).fill(0).map(x => new Array(n).fill(false)) for our initializations.

Please see the described solution in JavaScript below.

1
2javascript
3var pacificAtlantic = function(matrix) {
4    if (!matrix || matrix.length === 0) return [];
5
6    let m = matrix.length, n = matrix[0].length;
7    let p_ocean = new Array(m).fill(0).map(x => new Array(n).fill(false));
8    let a_ocean = new Array(m).fill(0).map(x => new Array(n).fill(false));
9    let res = [];
10    
11    for(let i = 0; i < m; i++){
12        dfs(matrix, p_ocean, i, 0, -1);
13        dfs(matrix, a_ocean, i, n - 1, -1);
14    }
15    
16    for(let i = 0; i < n; i++) {
17        dfs(matrix, p_ocean, 0, i, -1);
18        dfs(matrix, a_ocean, m - 1, i, -1);
19    }
20    
21    for(let i = 0; i < m; i++) {
22        for(let j = 0; j < n; j++) {
23            if(p_ocean[i][j] && a_ocean[i][j]) {
24                res.push([i, j]);
25            }
26        }
27    }
28    return res;
29};
30
31var dfs = function(matrix, ocean, i, j, height) {
32    let m = matrix.length, n = matrix[0].length;
33    if(i < 0 || i >= m || j < 0 || j >= n || ocean[i][j] || matrix[i][j] < height) return;
34    ocean[i][j] = true;
35    dfs(matrix, ocean, i - 1, j, matrix[i][j]);
36    dfs(matrix, ocean, i + 1, j, matrix[i][j]);
37    dfs(matrix, ocean, i, j - 1, matrix[i][j]);
38    dfs(matrix, ocean, i, j + 1, matrix[i][j]);
39};
40
41console.log(pacificAtlantic([[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]]))

The JavaScript solution follows the same concept as the Python solution, but it requires modifications due to syntactical differences between the languages. This solution also starts by running a DFS from all the borders, but it does not use visited arrays. Instead, it modifies the matrix in-place, which reduces the space complexity of the solution.