A grid contains land (L) and water (W). Return the size (number of cells) of the
smallest island. Assume there is at least one island.
minimumIsland(grid)
Input format: rows separated by |.
LLWW|WLWW|WWWL // → 1 (islands of size 3 and 1)
LLWWW|WWWLL|WWWLW // → 2
L // → 1
This uses the exact same idea as counting islands: treat the grid as an implicit graph, scan every cell, and flood-fill each unvisited island while marking its cells visited. The only change is what you do with each island once found — instead of just counting it, you need its size.
The flood-fill needs to report a count of cells touched, not just mark and return nothing. Visiting one land cell contributes 1, plus whatever sizes come back from recursively flood-filling each unvisited land neighbour. A neighbour out of bounds, water, or already visited contributes 0.
As you discover each island, compare its size against the smallest seen so far. A common pitfall: initializing the running minimum to 0 — since 0 is smaller than every real island, it never gets replaced, and you'd wrongly report 0. Instead, initialize it from the first island's size, or use a sentinel meaning "nothing found yet" and check for it explicitly. Same class of bug as seeding a running maximum with 0 in an all-negative array.
Land cells can form loops, so without a visited set the flood-fill could revisit cells repeatedly, both running forever and inflating the reported size. Marking a cell visited the instant it's counted guarantees it contributes to exactly one island's size, exactly once.
def minimum_island(grid):
rows = len(grid)
cols = len(grid[0])
visited = [[False] * cols for _ in range(rows)]
def size(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols:
return 0
if grid[r][c] != "L" or visited[r][c]:
return 0
visited[r][c] = True
return 1 + size(r + 1, c) + size(r - 1, c) + size(r, c + 1) + size(r, c - 1)
min_size = -1
for r in range(rows):
for c in range(cols):
if grid[r][c] == "L" and not visited[r][c]:
s = size(r, c)
if min_size == -1 or s < min_size:
min_size = s
return min_size
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.