#695

Medium

auto_awesomeArray plus Depth-First Search

LeetCode Problem Workspace

Max Area of Island

Find the largest connected land area in a binary grid using array traversal and depth-first search efficiently.

array depth first search breadth first search union find matrix

Problem Statement

Given an m x n binary matrix grid, an island is a set of 1's connected 4-directionally (up, down, left, right). All edges of the grid are surrounded by water. Your task is to find the size of the largest island in the grid.

Return the maximum area of an island. If no island exists, return 0. Each island's area is the total number of 1's it contains, and connectivity must be strictly 4-directional.

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

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

Example details omitted.

Constraints

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

Solution Approach

Depth-First Search (DFS) Traversal

Iterate over each cell in the grid. When a 1 is found, launch a DFS to mark all connected land cells as visited while counting the area. Update the maximum area after each DFS. This ensures every island is explored completely without double-counting.

Breadth-First Search (BFS) Alternative

Use a queue to perform BFS from each unvisited land cell. Enqueue neighboring 1's and count the cells until the queue is empty. This achieves the same island area computation while avoiding deep recursion, useful for grids approaching recursion limits.

Union-Find Optimization

Treat each land cell as a node in a union-find structure. Merge connected neighbors to identify island sets. Track the size of each set during unions to maintain the maximum island area. This reduces repeated searches but requires extra space for the parent and size arrays.

Complexity Analysis

Metric	Value
Time	O(R*C)
Space	O(R*C)

Time complexity is O(R C) because each cell is visited once in DFS/BFS. Space complexity is O(R C) in the worst case due to recursion stack or queue for DFS/BFS or storage arrays for union-find.

What Interviewers Usually Probe

Looking for DFS traversal and marking visited cells correctly.
Ensuring you handle edge boundaries without out-of-bounds errors.
Tracking maximum area dynamically while traversing each island.

Common Pitfalls or Variants

Common pitfalls

Counting diagonally connected 1's incorrectly as part of an island.
Failing to mark visited cells, leading to overcounting areas.
Stack overflow on large grids when using naive DFS recursion.

Follow-up variants

Compute the number of islands instead of the largest area.
Find the largest island allowing diagonal connectivity.
Determine the perimeter of the largest island rather than area.

FAQ

What is the recommended approach for Max Area of Island?

DFS is preferred for grid traversal in this problem, as it efficiently counts connected 1's while matching the array plus DFS pattern.

Can BFS be used instead of DFS?

Yes, BFS works by exploring neighbors iteratively, avoiding recursion depth limits while producing the same maximum area result.

What if the grid has no land cells?

The function should return 0, since no islands exist, ensuring proper handling of empty or water-only grids.

How does union-find compare to DFS/BFS here?

Union-find can merge connected cells into sets and track maximum sizes, but it uses extra memory and may be overkill for small grids.

What are common mistakes in this problem pattern?

Including diagonals, missing edge checks, or failing to mark visited cells are typical errors when solving array plus DFS grid problems.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        def dfs(i: int, j: int) -> int:
            if grid[i][j] == 0:
                return 0
            ans = 1
            grid[i][j] = 0
            dirs = (-1, 0, 1, 0, -1)
            for a, b in pairwise(dirs):
                x, y = i + a, j + b
                if 0 <= x < m and 0 <= y < n:
                    ans += dfs(x, y)
            return ans

        m, n = len(grid), len(grid[0])
        return max(dfs(i, j) for i in range(m) for j in range(n))

Continue Practicing

#778 swim in rising water #827 making a large island #959 regions cut by slashes