LeetCode: Pacific Atlantic Water Flow Solution

Approach

Flow backward, from pacific/atlantic

Result is the intersection

Implementation

```.css-ds3kc{display:table-row;}.css-1t8atru{display:table-cell;opacity:0.5;padding-right:var(--chakra-space-6);-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none;text-align:right;}1.css-2qghsv{display:table-cell;}/**2 * @param {number[][]} matrix3 * @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 res28  }29
30  const dfs = (i, j, visited) => {31    const pair = `\${i}-\${j}`32    if (visited.has(pair)) {33      return34    }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}```

leetcode

graph

dfs

bfs

Next Post

LeetCode: Word Subsets

Mar 27, 2021

Search Posts