DSA & System Design

Number of Islands

MediumGraph BFS and DFSUnion-Find (Disjoint Set Union)

You are given a map as an m x n grid of strings, where "1" is land and "0" is water. An island is a group of land cells joined horizontally or vertically; cells that only touch at a corner are not joined. Everything outside the grid is water.

Return the number of islands.

You may modify grid. The grid can also be empty ([]), in which case there are no islands.

Constraints

  • 0 <= m <= 300 and, when m > 0, 1 <= n <= 300
  • grid[r][c] is the string "0" or "1"

Examples

Example 1

Input: grid = [["1","1","0","0","0"],["1","1","0","1","0"],["0","0","0","1","1"],["0","1","0","0","0"]]
Output: 3

Three islands: the 2×2 block at the top left, the bent piece of three cells on the right, and the single cell at the bottom.

Example 2

Input: grid = [["1","1","1","1","0"],["0","0","0","1","0"],["1","1","0","1","0"],["1","1","1","1","0"]]
Output: 1

The land winds around the water in the middle, but every 1 is connected to the others through up/down/left/right steps: one island.

Example 3

Input: grid = [["1","0"],["0","1"]]
Output: 2

The two 1s touch only at a corner. Diagonal cells are not connected, so they are two islands.

JavaScript you'll use: Graphs and grids in JavaScript Stacks, queues and deques

/**
 * @param {string[][]} grid
 * @return {number}
 */
function numIslands(grid) {
  
}

Ctrl/⌘ + ' runs the examples, Ctrl/⌘ + Enter submits. Use console.log freely: output shows under Console. In the editor, press Esc then Tab to move focus out.