Max Area of Island

This is Number of Islands with a twist: instead of just counting islands, each flood fill needs to report how many cells it covered, and we keep a running maximum across every island found.

DFS with a Visited Set

Time O(m·n)Space O(m·n)

Scan every cell. When unvisited land is found, flood fill outward (up/down/left/right), counting the land cells along the way, and update the best area seen so far. A separate visited set keeps each island from being counted twice.

class Solution:
    def maxAreaOfIsland(self, grid: list[list[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        visited = set()

        def dfs(r, c):
            if (
                r < 0 or r >= rows or c < 0 or c >= cols
                or grid[r][c] == 0 or (r, c) in visited
            ):
                return 0
            visited.add((r, c))
            area = 1
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                area += dfs(r + dr, c + dc)
            return area

        best = 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 1 and (r, c) not in visited:
                    best = max(best, dfs(r, c))
        return best

Each cell contributes 1 to the area of exactly the island it belongs to, and the recursion naturally sums those contributions as it unwinds. Correct and O(m·n), but the visited set duplicates information already present in the grid.

DFS by Sinking Islands (In-Place)

OptimalTime O(m·n)Space O(m·n)

Drop the separate set: flip each visited land cell to 0 the moment we step on it. A sunk cell can never be miscounted as unvisited land again, so the grid itself becomes the visited-tracker.

class Solution:
    def maxAreaOfIsland(self, grid: list[list[int]]) -> int:
        rows, cols = len(grid), len(grid[0])

        def dfs(r, c):
            if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == 0:
                return 0
            grid[r][c] = 0  # sink this land so it is never recounted
            area = 1
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                area += dfs(r + dr, c + dc)
            return area

        best = 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 1:
                    best = max(best, dfs(r, c))
        return best

Watch the row-major scan find land, sink the whole island to 0 so the grid itself tracks what is seen, and keep the running best area on [[1,1,0],[0,1,0],[0,0,1]].

grid

area = 0best = 0scan = (0,0)

1 / 8

landwater

seenresultcurrent

Scan cells row by row. At each unvisited 1, flood fill the island while sinking every cell to 0, and count the cells.

Why it’s correct: flood-filling from a cell visits exactly the cells reachable through land, so the running total during one flood fill is exactly that island’s area; taking the max across every flood fill gives the largest island overall. Complexity: every cell is visited and sunk at most once, each doing O(1) work per neighbor check, so O(m·n) time. Space is dominated by the recursion stack, which in the worst case (one winding island spanning the grid) can hold all m·n cells, giving O(m·n) space — but without a second full-grid data structure alongside it.

Max Area of Island

DFS with a Visited Set

DFS by Sinking Islands (In-Place)

More Graphs practice