Max Area of Island

mediumGraphs: BFS / DFS208 stepsJava · Python · C++

Find the largest island by cell count. Same as counting islands, but each DFS returns the number of cells it sank: 1 for the current cell plus the areas from its four neighbours.

▶ Watch the animated trace

Traced input: grid = [[1,1,0,0],[1,0,0,1],[0,0,1,1],[0,0,1,0]] → 4. Original problem: neetcode.io/problems/max-area-of-island

Complexity

BestO(m·n)

AverageO(m·n)

WorstO(m·n)

SpaceO(m·n)

Every cell is visited once.

Key idea

DFS returns the area of the island it explores.
Sink cells as you go (set to 0) so they aren't counted twice.
Keep the maximum area across all islands.

Common mistakes

Returning 0 when no land exists is correct; don't return -1.
Forgetting to mark visited before recursing.

Solution

Java

// DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}: down, up, right, left
int maxAreaOfIsland(int[][] grid) {
    int best = 0;
    for (int r = 0; r < grid.length; r++) {
        for (int c = 0; c < grid[0].length; c++) {
            if (grid[r][c] == 1) {
                int area = area(grid, r, c);
                best = Math.max(best, area);
            }
        }
    }
    return best;
}

int area(int[][] grid, int r, int c) {
    if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length || grid[r][c] != 1) return 0;
    grid[r][c] = 0;
    int total = 1;
    for (int[] d : DIRS) total += area(grid, r + d[0], c + d[1]);
    return total;
}

Python

# DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]: down, up, right, left
def maxAreaOfIsland(grid: List[List[int]]) -> int:
    def area(r: int, c: int) -> int:
        if r < 0 or c < 0 or r >= len(grid) or c >= len(grid[0]) or grid[r][c] != 1: return 0
        grid[r][c] = 0
        return 1 + sum(area(r + dr, c + dc) for dr, dc in DIRS)

    best = 0
    for r in range(len(grid)):
        for c in range(len(grid[0])):
            if grid[r][c] == 1:
                best = max(best, area(r, c))
    return best

C++

// DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}: down, up, right, left
int area(vector<vector<int>>& grid, int r, int c) {
    if (r < 0 || c < 0 || r >= (int)grid.size() || c >= (int)grid[0].size() || grid[r][c] != 1) return 0;
    grid[r][c] = 0;
    int total = 1;
    for (auto& d : DIRS) total += area(grid, r + d[0], c + d[1]);
    return total;
}

int maxAreaOfIsland(vector<vector<int>>& grid) {
    int best = 0;
    for (int r = 0; r < (int)grid.size(); r++) {
        for (int c = 0; c < (int)grid[0].size(); c++) {
            if (grid[r][c] == 1) {
                best = max(best, area(grid, r, c));
            }
        }
    }
    return best;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
No land Max stays 0.	`grid = [[0, 0, 0]]`	`0`
Single cell One island of area 1.	`grid = [[1]]`	`1`
Two equal islands Both have area 1.	`grid = [[1, 0, 1]]`	`1`