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

Tracing a small grid [[1,1,0],[0,1,0],[0,0,1]] (row-major scan, flood-filling each island found and tracking the running max area):

1 / 6

landwatervisitedcurrent

Scan hits land at (0,0). Start a DFS flood fill, area so far = 1.

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.