Max Area of Island

You are given an m × n binary matrix grid. An island is a group of 1s connected 4-directionally. Return the maximum area of an island in the grid. If there is no island, return 0.

Practice Link

Example#

grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]

The red island has area 6. The orange islands have areas 1, 4, 3, 5, and 5. Output: 6

Note: the answer is not 11 — the two groups of 1s near columns 8–10 are not 4-directionally connected to each other (there is a gap at row 3, col 9).

DFS — Flood Fill#

For each unvisited land cell, launch a DFS that marks every reachable cell as visited (sets it to 0) and counts the area of that island. Track the running maximum across all islands.

Why mark as 0? Mutating the grid avoids a separate visited array and makes the visited check O(1) in-place.

class Solution {
public:
    int maxArea = 0;
    int dx[4] = {1, 0, -1, 0};
    int dy[4] = {0, 1, 0, -1};

    bool isValid(int x, int y, int m, int n) {
        return x >= 0 && x < m && y >= 0 && y < n;
    }

    void dfs(vector<vector<int>>& grid, int row, int col, int m, int n, int& area) {
        area++;
        maxArea = max(maxArea, area);
        grid[row][col] = 0;  // mark visited in-place

        for (int dir = 0; dir < 4; dir++) {
            int nRow = row + dx[dir];
            int nCol = col + dy[dir];
            if (isValid(nRow, nCol, m, n) && grid[nRow][nCol] == 1)
                dfs(grid, nRow, nCol, m, n, area);
        }
    }

    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();

        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (grid[i][j] == 1) {
                    int area = 0;
                    dfs(grid, i, j, m, n, area);
                }

        return maxArea;
    }
};

Time Complexity: O(m × n) — every cell is visited at most once
Space Complexity: O(m × n) — recursion stack depth in worst case (all land)

Common pitfalls#

1. y <= n instead of y >= n in bounds check
y <= n is true for every valid index (0 through n-1) — it rejects all valid cells and silently produces wrong answers with no crash. The correct column check is y >= n.

2. Initialising maxArea = INT_MIN
If the grid has no islands the outer loop never calls DFS, and INT_MIN is returned instead of 0. Initialise to 0.

3. Sharing area across islands
area must be declared fresh (int area = 0) inside the outer loop for each new island. If declared outside, counts from previous islands bleed in.