LeetCode: Number of Islands Solution

To be consistent, first find out how to make it easy

Approach

After detecting a piece of an island (cell with value `1`), recursively spread through all vertical and horizontal directions to discover a full island

Could use any ways to mark the visited state

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;}var numIslands = function (grid) {2  const [m, n] = [grid.length, grid[0].length]3
4  let res = 05
6  const isValidCell = (i, j) => 0 <= i && i < m && 0 <= j && j < n7
8  const recursion = (i, j) => {9    if (isValidCell(i, j) && grid[i][j] === "1") {10      grid[i][j] = 011      recursion(i + 1, j)12      recursion(i, j + 1)13      recursion(i - 1, j)14      recursion(i, j - 1)15      return16    }17  }18
19  for (let i = 0; i < m; i++) {20    for (let j = 0; j < n; j++) {21      if (grid[i][j] === "1") {22        recursion(i, j)23        res++24      }25    }26  }27
28  return res29}```

Original problem

leetcode

array

matrix

dfs

recursion

Next Post

LeetCode: Happy Number

Use a Set to detect cycle

Previous Post

LeetCode: Validate Binary Search Tree

Traverse in-order and validate the traversed result

Search Posts