Largest Island Area
Problem
A map is a grid of 0s (water) and 1s (land). An island is a group of land cells connected up, down, left or right; diagonal neighbours do not connect. The area of an island is its number of cells. Return the area of the largest island, or 0 if there is no land.
Examples
Input: grid = [[1, 1, 0, 0], [1, 0, 0, 1], [0, 0, 1, 1], [0, 0, 1, 0]]
Output: 4
Why: the top-left island has 3 cells and the one on the right has 4Input: grid = [[1, 0, 1], [0, 1, 0], [1, 0, 1]]
Output: 1
Why: diagonal cells do not join, so there are five islands of one cellInput: grid = [[0, 0], [0, 0]]
Output: 0
Why: edge case, no land at allHints
0 / 3
This is island counting with one change: instead of counting how many islands you start, measure each one as you explore it.
Scan every cell. When you hit land, explore the whole island from it with a stack or a queue and count the cells you visit.
Mark a cell as visited the moment you push it, for example by setting it to 0, so it is never counted twice and never starts a second search. Keep the largest count.
Solution
Every land cell belongs to exactly one island, and a flood fill from any of its cells visits the whole island and nothing else. The outer scan starts a fill only on land that has not been visited yet, and the fill counts cells as it pops them. Sinking a cell (setting it to 0) as soon as it is pushed is the visited mark, so no cell is pushed twice. An explicit stack keeps a large island from hitting Python's recursion limit. Each cell is scanned once and pushed at most once, so time is O(rows × cols); the stack can hold O(rows × cols) cells in the worst case. The function works on a copy so the caller's grid is left alone.
def largest_island(grid):
grid = [row[:] for row in grid] # sink cells in a copy
rows, cols = len(grid), len(grid[0])
best = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] != 1:
continue
grid[r][c] = 0
stack, area = [(r, c)], 0
while stack:
y, x = stack.pop()
area += 1
for ny, nx in ((y + 1, x), (y - 1, x), (y, x + 1), (y, x - 1)):
if 0 <= ny < rows and 0 <= nx < cols and grid[ny][nx] == 1:
grid[ny][nx] = 0 # visited the moment it is pushed
stack.append((ny, nx))
best = max(best, area)
return best
print(largest_island([[1, 1, 0, 0], [1, 0, 0, 1], [0, 0, 1, 1], [0, 0, 1, 0]])) # -> 4
print(largest_island([[1, 0, 1], [0, 1, 0], [1, 0, 1]])) # -> 1
print(largest_island([[0, 0], [0, 0]])) # -> 0Stuck on the idea rather than the code? Number of Islands covers it.