Number of Islands
Solve and submit on LeetCode to build your LeetCode profile. Use the hints here when you need guidance.
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
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)
