Challenge: number of islands
Count connected groups of '1's in a 2D grid using DFS in O(m×n) time.
- Count islands in a 2D grid using DFS in O(m×n) time
Optional challenge. A classic grid traversal problem — the efficiency check confirms you are not revisiting cells unnecessarily.
Given a 2D grid of '1' (land) and '0' (water) characters, count the number
of islands. An island is a group of adjacent '1's connected horizontally or
vertically, surrounded by water or grid edges.
num_islands([["1","1","0"],["1","1","0"],["0","0","1"]]) → 2.
Hint: iterate over every cell. When you find an unvisited '1', increment
the count and run DFS from that cell, marking every reachable land cell as
visited in-place by setting it to '0'. No visited set needed.
Write num_islands(grid) returning the number of connected groups of "1"s. Use DFS, marking cells in-place. The function may mutate the grid.
num_islands([["1","1","0"],["1","1","0"],["0","0","1"]]) → 2num_islands([["1","1","1"],["0","1","0"],["1","1","1"]]) → 1