graphs · Problem 2 of 2

Number of Islands

medium

Amazon

Google

Meta

Microsoft

Bloomberg

Given an m x n 2D binary grid representing a map of "1"s (land) and "0"s (water), return the total number of distinct islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically (4-directional connectivity). You may assume all four edges of the grid are entirely surrounded by water.

numIslands([
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]) -> 1

numIslands([
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]) -> 3

Your solution

input

Runs your code and animates it without grading anything. Change the input to see what it does on a case the tests do not cover.

Running is free — Submit is what records it. Or press ⌘↩

Tests

4 cases, 1 hidden

call	type	expected	result
numIslands([["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]])	single island	1	—
numIslands([["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]])	three islands	3	—
numIslands([["0","0","0"],["0","0","0"]])	all water	0	—
withheld	hidden	withheld	—

Hidden cases run too — their inputs aren't listed here, so aim for a general solution rather than one fitted to the cases above.

Complexity

target time: O(m × n)
target space: O(m × n) call stack in the worst case (e.g. grid filled entirely with land)

Every cell in the matrix is visited at most twice (once in outer iteration, once during DFS traversal).

Hints

Stuck? Hints open one at a time, each giving a little more away.

3 hints left