A grid contains land (L) and water (W). An island is a group of L cells
connected horizontally or vertically (not diagonally). Return the number of
islands.
islandCount(grid)
Input format: rows separated by |, each a string of L/W. For example
LLWW|WLWW|WWWL.
LLWW|WLWW|WWWL // → 2
WWW|WWW // → 0
LWL|WWW|LWL // → 4
This looks like a 2D grid of characters, but it's the same "count connected components" problem as any graph — the grid is a graph in disguise. Each cell is a node. Two cells connect if they're adjacent horizontally or vertically and both are land. There's no adjacency list to read; the structure is implied by coordinates — a cell at (r, c) connects to its neighbours above, below, left, and right, as long as those exist and are also land.
Once you see it this way, the solution is component counting on this implicit graph: scan every cell, and whenever you find an unvisited land cell, that's a new island. Fully explore everything connected to it (a "flood fill," identical in spirit to a graph traversal), marking every cell in it visited, then move on.
Land cells can form loops — a 2×2 block lets you flood-fill back and forth forever. Tracking visited cells (a same-shaped grid of booleans works well) prevents this and stops you re-adding cells you've already counted.
Unlike an adjacency list, where an invalid neighbour just wouldn't appear, here you must explicitly check that a neighbouring row and column are in bounds before looking at what's there. Every step into a neighbour checks, in order: in bounds? land? already visited? Only if all three pass do you mark it visited and continue.
Each full flood-fill is exactly one island, since it touches every land cell reachable through adjacent land — the definition of one connected component. The number of fresh flood-fills you start is exactly the number of islands.
def island_count(grid):
if len(grid) == 0:
return 0
rows = len(grid)
cols = len(grid[0])
visited = [[False] * cols for _ in range(rows)]
def explore(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols:
return
if grid[r][c] != "L" or visited[r][c]:
return
visited[r][c] = True
explore(r + 1, c)
explore(r - 1, c)
explore(r, c + 1)
explore(r, c - 1)
count = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == "L" and not visited[r][c]:
count += 1
explore(r, c)
return count
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.