Number of Islands
Medium· DFS· BFS· Grid
Problem
Given a grid of "1" (land) and "0" (water), count the islands. An island is a group of land cells connected horizontally or vertically, and everything outside the grid is water.
Examples
Input: grid = [["1","1","0","0"],["1","0","0","1"],["0","0","1","1"]]
Output: 2
Input: grid = [["1","0","1"],["0","1","0"],["1","0","1"]]
Output: 5
Diagonal neighbours do not connect, so every land cell is its own island.
Constraints
- • 1 <= m, n <= 300
- • grid[i][j] is "0" or "1"
Hints & approach
Hint 1
Each island is a connected component in a grid graph.
Hint 2
Scan the grid; the first time you hit unvisited land, you have found a new island.
Hint 3
Flood the whole island from there so you never count it again.
Approachtry the hints first
Loop over every cell. When a cell is land, increment the count and run DFS or BFS from it, turning every reachable land cell into water (or marking it visited). Each cell is flooded at most once, so the total work is linear in the grid size. Union-find over land cells is an alternative that also works well for streaming updates.
Time O(m * n) · Space O(m * n)