Max Area of Island

LeetCode 695 | Difficulty: Medium

Medium

Problem Description

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.

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 answer is not 11, because the island must be connected 4-directionally.

Example 2:

Input: grid = [[0,0,0,0,0,0,0,0]]
Output: 0

Constraints:

- `m == grid.length`

- `n == grid[i].length`

- `1 <= m, n <= 50`

- `grid[i][j]` is either `0` or `1`.

Topics: Array, Depth-First Search, Breadth-First Search, Union-Find, Matrix

---

Approach

BFS (Graph/Matrix)

Use a queue to explore nodes level by level. Start from source node(s), visit all neighbors before moving to the next level. BFS naturally finds shortest paths in unweighted graphs.

When to use

Shortest path in unweighted graph, level-order processing, spreading/flood fill.

Union-Find

Maintain disjoint sets with two operations: find (which set does element belong to?) and union (merge two sets). Use path compression and union by rank for near O(1) amortized operations.

When to use

Connected components, cycle detection in undirected graphs, grouping elements.

Matrix

Treat the matrix as a 2D grid. Common techniques: directional arrays (dx, dy) for movement, BFS/DFS for connected regions, in-place marking for visited cells, boundary traversal for spiral patterns.

When to use

Grid traversal, island problems, path finding, rotating/transforming matrices.

---

Solutions

Solution 1: C# (Best: 112 ms)

Metric	Value
Runtime	112 ms
Memory	28.4 MB
Date	2020-11-01

Solution

public class Solution {
    public int MaxAreaOfIsland(int[][] grid) {
        int m = grid.Length;
    int n = grid[0].Length;
    bool[,] visited = new bool[m,n];
    int len = 0;
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if(grid[i][j] == 1 && !visited[i,j])
            {
                len = Math.Max(len, MaxAreaDfs(grid, visited, i, j));
            }
        }
    }
    
    return len;

}

public int MaxAreaDfs(int[][] grid, bool[,] visited, int i, int j)
{
    if(i<0 || i>=grid.Length || j<0 || j>=grid[0].Length || grid[i][j] == 0 || visited[i,j])
    return 0;
    int area = 1;
    visited[i, j] = true;
    area += MaxAreaDfs(grid, visited, i-1, j);
    area += MaxAreaDfs(grid, visited, i+1, j);
    area += MaxAreaDfs(grid, visited, i, j-1);
    area += MaxAreaDfs(grid, visited, i, j+1);
    return area;
}
}

📜 1 more C# submission(s)

Submission (2021-09-01) — 167 ms, 28.3 MB

public class Solution {
    public int MaxAreaOfIsland(int[][] grid) {
        int m = grid.Length;
    int n = grid[0].Length;
    bool[,] visited = new bool[m,n];
    int len = 0;
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if(grid[i][j] == 1 && !visited[i,j])
            {
                len = Math.Max(len, MaxAreaDfs(grid, visited, i, j));
            }
        }
    }
    
    return len;

}

public int MaxAreaDfs(int[][] grid, bool[,] visited, int i, int j)
{
    if(i<0 || i>=grid.Length || j<0 || j>=grid[0].Length || grid[i][j] == 0 || visited[i,j])
    return 0;
    int area = 1;
    visited[i, j] = true;
    area += MaxAreaDfs(grid, visited, i-1, j);
    area += MaxAreaDfs(grid, visited, i+1, j);
    area += MaxAreaDfs(grid, visited, i, j-1);
    area += MaxAreaDfs(grid, visited, i, j+1);
    return area;
}
}

---

Complexity Analysis

Approach	Time	Space
Graph BFS/DFS	$O(V + E)$	$O(V)$
Union-Find	$O(n × α(n))$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.