Graphs · 029Medium
Number of Islands
Given an m x n binary grid where '1' is land and '0' is water, return the number of islands. An island is land connected 4-directionally and surrounded by water.
Constraints
- 1 <= m, n <= 300
- grid[i][j] is '0' or '1'.
Examples
numIslands([["1","1","0"],["1","1","0"],["0","0","1"]]) -> 2 numIslands([["0"]]) -> 0 numIslands([["1"]]) -> 1 numIslands([["1","1"],["1","1"]]) -> 1 // all land, one island numIslands([["1","0"],["0","1"]]) -> 2 // diagonals do not connect numIslands([["1","0","1","0","1"]]) -> 3 // a single row
Edge cases
- A grid of all water, or all land.
- Diagonal neighbors do NOT connect.
Show the target complexity (spoiler)
- Naive
- Repeated scans without marking visited cells revisit the same land endlessly.
- Target
- O(m * n) time — scan every cell; on unvisited land, flood-fill (DFS or BFS) the whole island and count 1.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/08-graphs/029-number-of-islands.js ./practice c 029