Max Area of Island

Problem Description

You are given an m x n binary matrix grid. An island is a group of 1s (land) connected 4-directionally (horizontal or vertical). You may assume all four edges of the grid are surrounded by water.

Return the maximum area of an island in grid. If there is no island, return 0.

Examples

Constraints

• m == grid.length
• n == grid[i].length
• 1 ≤ m, n ≤ 50
• grid[i][j] is 0 or 1

DFS That Returns Area Instead of Just Counting

Number of Islands counts connected components. Max Area of Island measures the size of each component and returns the largest. The DFS is nearly identical, but instead of just marking cells visited, you accumulate the count of cells and return it.

Mark visited cells by setting grid[r][c] = 0 in-place. This avoids a separate visited array and works because the grid is only used for exploration (no need to restore original values after the function returns).

Solution: DFS (Recursive)

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int maxArea = 0;
        for (int r = 0; r < grid.length; r++) {
            for (int c = 0; c < grid[0].length; c++) {
                if (grid[r][c] == 1) {
                    maxArea = Math.max(maxArea, dfs(grid, r, c));
                }
            }
        }
        return maxArea;
    }

    private int dfs(int[][] grid, int r, int c) {
        if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] == 0) {
            return 0;
        }
        grid[r][c] = 0; // mark visited

        return 1 + dfs(grid, r+1, c) + dfs(grid, r-1, c)
                 + dfs(grid, r, c+1) + dfs(grid, r, c-1);
    }
}

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

        def dfs(r: int, c: int) -> int:
            if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == 0:
                return 0
            grid[r][c] = 0  # mark visited
            return 1 + dfs(r+1, c) + dfs(r-1, c) + dfs(r, c+1) + dfs(r, c-1)

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

#include <vector>
#include <algorithm>

class Solution {
public:
    int maxAreaOfIsland(std::vector<std::vector<int>>& grid) {
        int maxArea = 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) {
                    maxArea = std::max(maxArea, dfs(grid, r, c));
                }
            }
        }
        return maxArea;
    }

private:
    int dfs(std::vector<std::vector<int>>& grid, int r, int c) {
        if (r < 0 || r >= (int)grid.size() || c < 0 || c >= (int)grid[0].size() || grid[r][c] == 0) {
            return 0;
        }
        grid[r][c] = 0;
        return 1 + dfs(grid, r+1, c) + dfs(grid, r-1, c)
                 + dfs(grid, r, c+1) + dfs(grid, r, c-1);
    }
};

Complexity Analysis:

• Time Complexity: O(m * n). Every cell is visited at most once.
• Space Complexity: O(m * n) in the worst case for the recursion stack (all cells are land in a zigzag pattern).

Where it breaks: for very large grids (m, n ~ 50 in this problem, but potentially larger elsewhere), deep recursion on a fully connected grid can hit the call stack limit. BFS iterates explicitly and avoids this.

Common Mistakes

• Checking grid[r][c] == 1 before marking as 0. Once you enter the DFS, mark the cell visited immediately at the top of the function, before making recursive calls. Some solutions delay the mark, causing cells to be visited multiple times.
• Forgetting the 4-directional constraint. This is 4-connected (up/down/left/right), not 8-connected (including diagonals).

Frequently Asked Questions

How is this different from Number of Islands? Number of Islands counts how many islands there are. Max Area of Island measures the size of each island and returns the maximum. Same DFS traversal, different return value.

Can this be solved with BFS? Yes. Use a queue instead of recursion. BFS processes cells level by level but visits the same set of cells. For this problem, both approaches have identical complexity.

← All Problems