mediumGraphsPure DSA~25 min
Cluster Island Count
A datacentre rack map is a grid where 1 marks a powered node and 0 an empty slot. Nodes that are vertically or horizontally adjacent form one connected cluster. Count how many distinct clusters the rack contains.
Problem
Given a grid of 0s and 1s, return the number of connected components ('islands') of 1s, using 4-directional adjacency.
Input
A grid with r rows and c columns (1 ≤ r, c ≤ 1000), each cell 0 or 1.
Output
A single integer — the number of islands.
Constraints
- 1 ≤ r, c ≤ 1000 (up to 10^6 cells)
- Adjacency is 4-directional (up/down/left/right)
- Diagonal cells are not connected
Examples
Example 1
Input
grid = [[1,1,0,0],[1,0,0,1],[0,0,1,1]]
Output
2
The top-left L-shape of 1s is one cluster; the bottom-right block (including the cell at row 1, col 3) is the second.
Example 2
Input
grid = [[0,0],[0,0]]
Output
0
No powered nodes, no clusters.