---

1. Problem Summary

You are given a 2D grid consisting of:

1 → land
0 → water

An island is defined as a group of connected 1s where connectivity is:

• vertical or horizontal (not diagonal)

Your task is to compute:

the size (number of cells) of the largest island in the grid

If there is no land at all, return:

0

Example:

Input:
[
 [0,0,1,0],
 [1,1,1,0],
 [0,1,0,0],
 [1,0,0,0]
]

Largest island area = 5

---

2. Key Insights

Insight 1: This is a connected-component counting problem

Each island is a connected region of 1s.

Insight 2: DFS or BFS can explore each island

Once starting from a land cell, explore all reachable land.

Insight 3: Must mark visited cells

To avoid recounting, we must mark visited:

• using a separate visited grid, or
• modifying grid by turning 1 into 0

Insight 4: Track area per island

During traversal, count number of cells visited in that island.

Insight 5: Update maximum after each island traversal

At end, return maximum area.

---

3. Approach

Depth-First Search (DFS) flood-fill

Steps:

1. Initialize maxArea = 0
2. Loop through every cell in grid
3. If cell is land (1):
   • call DFS to explore island
   • DFS returns area size
   • update maxArea
4. Return maxArea

DFS expansion checks four directions:

up, down, left, right

Boundary checks required.

---

4. Time and Space Complexity

Time Complexity:

O(R * C)

Every cell visited at most once.

Space Complexity:

O(R * C) in recursion worst case

DFS call stack may reach entire grid in worst case island.

---

5. Java Solution

class Solution {

    public int maxAreaOfIsland(int[][] grid) {
        int maxArea = 0;

        for (int row = 0; row < grid.length; row++) {
            for (int col = 0; col < grid[0].length; col++) {
                if (grid[row][col] == 1) {
                    int area = dfs(grid, row, col);
                    maxArea = Math.max(maxArea, area);
                }
            }
        }

        return maxArea;
    }

    private int dfs(int[][] grid, int row, int col) {
        if (row < 0 || row >= grid.length ||
            col < 0 || col >= grid[0].length ||
            grid[row][col] == 0) {
            return 0;
        }

        grid[row][col] = 0;

        int area = 1;

        area += dfs(grid, row + 1, col);
        area += dfs(grid, row - 1, col);
        area += dfs(grid, row, col + 1);
        area += dfs(grid, row, col - 1);

        return area;
    }
}

---

6. Dry Run Examples

Example 1

Input:

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

Single land cell → area = 1

Output:

1

---

Example 2

Input:

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

Island grouped → 4 cells

Output:

4

---

Example 3

Input:

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

Four isolated land cells
largest island = 1

Output:

1

---

Example 4

Input:

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

Largest island size = 5

Output:

5

---

Example 5

Input:

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

No land

Output:

0

---

7. Why This Solution Works

• DFS/BFS guarantees full exploration of each island
• Each cell visited only once
• Modifying grid avoids extra memory for visited
• Handles irregular island shapes
• Works for large grids efficiently

---

8. Common Mistakes

1. Counting diagonal neighbors (not allowed)
2. Forgetting boundary checks → index out of bounds
3. Not marking visited, causing infinite recursion
4. Resetting area incorrectly between islands
5. Misinterpreting problem as counting number of islands