Problem 579873 · medium · Phase 05 Advanced Algorithms & Graphs

Number of Islands

graphs · grid · bfs · dfs · flood fill

Grids are graphs in disguise: every cell is a node and its up/down/left/right neighbours are its edges. You never need to build the adjacency list; you compute neighbours on the fly.

Given an m x n grid of characters "1" (land) and "0" (water), return the number of islands. An island is a group of land cells connected horizontally or vertically (not diagonally). Assume all four edges of the grid are surrounded by water.

Examples

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

Input:  grid = [["1","0","1"],
                ["0","1","0"],
                ["1","0","1"]]
Output: 5
Explanation: diagonal cells do not touch

Constraints

  • 1 <= m, n <= 300
  • grid[i][j] is "0" or "1"
  • Target: O(m * n) time

Goals

  • Treat a 2D grid as an implicit graph where neighbours are the 4 adjacent cells
  • Flood-fill a region with BFS/DFS and mark cells so they are not counted twice
  • Check grid bounds before touching a neighbour
Starting Python…