Number of Islands
Medium · Graphs · Array · DFS · BFS · Union Find · Matrix
Problem
Given a 2-D grid of "1" (land) and "0" (water), count the islands.
An island is a group of land cells connected horizontally or vertically (not diagonally). The grid is surrounded by water on all sides.
Examples
Input: grid = [["1","1","0"],
["1","0","0"],
["0","0","1"]]
Output: 2The three connected cells on the left, plus the lone cell bottom-right.
Constraints
- 1 <= rows, cols <= 300
- grid[i][j] is "0" or "1"
Approaches
- Union-Find (disjoint set) — time O(rows · cols · α), space O(rows · cols)
Related problems
Start free on Cariara · Coding problems · System design studio
