Approach

Max Area of Island

Problem Statement

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

The area of an island is the number of cells with a value 1 in the island.

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

Examples

Example 1:

Input: 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]
]
Output: 6
Explanation: The maximum area is the island in the middle-right (6 cells).

Example 2:

Input: grid = [[0,0,0,0,0,0,0,0]]
Output: 0
Explanation: No islands exist.

Constraints

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

Approach: DFS (Depth-First Search)

Use DFS to explore each island and calculate its area. For each unvisited land cell (1), start a DFS to mark all connected land cells as visited and count the area. Track the maximum area found.

Algorithm:

Iterate through each cell in the grid
When a land cell (1) is found, start DFS
DFS marks current cell as visited (change to 0) and explores 4 directions
Return the area of current island
Keep track of maximum area

Time Complexity: O(m × n) - visit each cell once Space Complexity: O(m × n) - recursion stack in worst case

Solution

java

1class Solution {
2    // DFS Solution
3    public int maxAreaOfIsland(int[][] grid) {
4        if (grid == null || grid.length == 0) return 0;
5
6        int m = grid.length;
7        int n = grid[0].length;
8        int maxArea = 0;
9
10        for (int i = 0; i < m; i++) {
11            for (int j = 0; j < n; j++) {
12                if (grid[i][j] == 1) {
13                    int area = dfs(grid, i, j);
14                    maxArea = Math.max(maxArea, area);
15                }
16            }
17        }
18
19        return maxArea;
20    }
21
22    private int dfs(int[][] grid, int row, int col) {
23        int m = grid.length;
24        int n = grid[0].length;
25
26        // Boundary check and water check
27        if (row < 0 || row >= m || col < 0 || col >= n || grid[row][col] == 0) {
28            return 0;
29        }
30
31        // Mark as visited
32        grid[row][col] = 0;
33
34        // Calculate area: current cell + all 4 directions
35        int area = 1;
36        area += dfs(grid, row + 1, col);  // down
37        area += dfs(grid, row - 1, col);  // up
38        area += dfs(grid, row, col + 1);  // right
39        area += dfs(grid, row, col - 1);  // left
40
41        return area;
42    }
43}
44
45/**
46 * Time Complexity: O(m * n) where m is number of rows and n is number of columns
47 * - We visit each cell at most once
48 *
49 * Space Complexity: O(m * n)
50 * - Recursion stack can go as deep as m*n in worst case (entire grid is one island)
51 *
52 * Key Insights:
53 * - Use DFS to explore connected land cells
54 * - Mark cells as visited by setting to 0 (modifies input)
55 * - Each DFS call returns the area of the island component
56 * - Track maximum area across all islands
57 */
58