Count Island Blobs
Problem
A rectangular grid holds 1 for land and 0 for water. An island is a group of land cells connected to each other through shared edges, so cells touching only at a corner belong to different islands. Count how many separate islands the grid contains.
Examples
Input: [[1, 1, 0],
[0, 1, 0],
[0, 0, 1]]
Output: 2
Why: the corner-touching cell at the bottom right is its own islandInput: [[0, 0],
[0, 0]]
Output: 0
Why: edge case, a grid of pure water has no islandsInput: [[1]]
Output: 1
Why: edge case, a single land cell is a complete islandHints
0 / 3
A grid is a graph in disguise: each land cell is a node, and touching land cells are joined by an edge. The question then becomes a familiar one about groups.
You need a way to mark cells as already accounted for, otherwise the same island gets counted once per cell it contains.
Scan every cell in order. When you find unvisited land, add one to the count, then spread out from that cell through its four neighbours, marking every land cell you can reach as visited so the outer scan skips the rest of that island.
Solution
Each land cell is a node and edge-sharing land cells are connected, so counting islands is counting connected components. The outer scan starts a flood only at unvisited land, and the flood marks the entire component so the scan never counts it again. An explicit stack drives the flood, which avoids deep recursion on large grids. Time is O(rows times cols) since each cell is examined a constant number of times, and space is O(rows times cols) in the worst case.
def count_islands(grid):
if not grid: return 0
rows, cols, seen = len(grid), len(grid[0]), set()
def sink(r, c): # flood the whole blob from one cell
stack = [(r, c)]
while stack:
i, j = stack.pop()
for a, b in ((i+1, j), (i-1, j), (i, j+1), (i, j-1)):
if 0 <= a < rows and 0 <= b < cols and grid[a][b] == 1 and (a, b) not in seen:
seen.add((a, b)); stack.append((a, b))
total = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == 1 and (r, c) not in seen:
seen.add((r, c)); sink(r, c); total += 1 # a brand new island
return total
print(count_islands([[1, 1, 0], [0, 1, 0], [0, 0, 1]])) # -> 2
print(count_islands([[0, 0], [0, 0]])) # -> 0
print(count_islands([[1]])) # -> 1Stuck on the idea rather than the code? Connected Components covers it.