LeetCode: Pacific Atlantic Water Flow Solution

Approach

Flow backward, from pacific/atlantic

Result is the intersection

Implementation

1/**
2 * @param {number[][]} matrix
3 * @return {number[][]}
4 */
5var pacificAtlantic = function (matrix) {
6  if (matrix.length === 0) {
7    return []
8  }
9
10  const [M, N] = [matrix.length, matrix[0].length]
11  const pacificVisited = new Set()
12  const atlanticVisited = new Set()
13  const directions = [
14    [1, 0],
15    [-1, 0],
16    [0, 1],
17    [0, -1],
18  ]
19
20  const intersection = (setA, setB) => {
21    let res = new Set()
22    for (let el of setB) {
23      if (setA.has(el)) {
24        res.add(el)
25      }
26    }
27    return res
28  }
29
30  const dfs = (i, j, visited) => {
31    const pair = `${i}-${j}`
32    if (visited.has(pair)) {
33      return
34    }
35    visited.add(pair)
36    for (const direction of directions) {
37      const [nextI, nextJ] = [i + direction[0], j + direction[1]]
38      if (
39        0 <= nextI &&
40        nextI < M &&
41        0 <= nextJ &&
42        nextJ < N &&
43        matrix[nextI][nextJ] >= matrix[i][j]
44      ) {
45        dfs(nextI, nextJ, visited)
46      }
47    }
48  }
49
50  for (let row = 0; row < M; row++) {
51    dfs(row, 0, pacificVisited)
52    dfs(row, N - 1, atlanticVisited)
53  }
54  for (let col = 0; col < N; col++) {
55    dfs(0, col, pacificVisited)
56    dfs(M - 1, col, atlanticVisited)
57  }
58
59  return [...intersection(pacificVisited, atlanticVisited)].map(pair =>
60    pair.split("-").map(Number)
61  )
62}