Problem Overview

You are given a binary matrix grid of size m x n.

• 1 represents land.

• 0 represents water.

An island is a group of connected 1s in four directions: up, down, left, and right.
You need to find the area of the largest island — the maximum number of connected land cells.
If there are no islands, return 0.

Intuition

We can think of the grid as a map.
Our goal is to find all connected groups of land (1s) and calculate their sizes.
This can be done using Depth First Search (DFS), which explores all connected cells starting from one point.

When we find a 1, we:

1. Mark it as visited (set it to 0 so we don’t count it again).

2. Explore its four neighboring cells.

3. Count how many cells are part of this island.

We repeat this process for the entire grid and keep track of the largest island area.

Step-by-Step Explanation

1. DFS Function

We create a helper function dfs that takes the grid and the current cell coordinates (i, j).
If the current cell is out of bounds or water (0), we return 0.
Otherwise, we mark the cell as visited and explore its four directions.

int dfs(vector<vector<int>>& grid, int i, int j) {
    if (i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size() || grid[i][j] == 0)
        return 0;

    grid[i][j] = 0; // mark as visited
    int area = 1;

    area += dfs(grid, i + 1, j); // down
    area += dfs(grid, i - 1, j); // up
    area += dfs(grid, i, j + 1); // right
    area += dfs(grid, i, j - 1); // left

    return area;
}

2. Main Function

We iterate over all cells in the grid.
Whenever we find land (1), we call dfs to calculate that island’s area.
We update maxArea if we find a larger one.

int maxAreaOfIsland(vector<vector<int>>& grid) {
    int maxArea = 0;
    for (int i = 0; i < grid.size(); i++) {
        for (int j = 0; j < grid[0].size(); j++) {
            if (grid[i][j] == 1) {
                int area = dfs(grid, i, j);
                maxArea = max(maxArea, area);
            }
        }
    }
    return maxArea;
}

Example

Consider the grid:

[[0,0,1,0],
 [1,1,1,0],
 [0,1,0,0]]

• The island starting at (0,2) connects with several cells around it.

• The total connected land cells = 5.

• The answer is 5.

Time and Space Complexity

• Time Complexity: O(m × n), since each cell is visited once.

• Space Complexity: O(m × n) in the worst case (due to recursion stack).

Final Code

class Solution {
public:
    int dfs(vector<vector<int>>& grid, int i, int j) {
        if (i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size() || grid[i][j] == 0)
            return 0;
        grid[i][j] = 0;
        int area = 1;
        area += dfs(grid, i + 1, j);
        area += dfs(grid, i - 1, j);
        area += dfs(grid, i, j + 1);
        area += dfs(grid, i, j - 1);
        return area;
    }

    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int maxArea = 0;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == 1) {
                    int area = dfs(grid, i, j);
                    maxArea = max(maxArea, area);
                }
            }
        }
        return maxArea;
    }
};