How do you solve Max Area of Island?

Use DFS to explore each island starting from unvisited land cells. Maintain a visited set to track explored cells. For each island, recursively visit all connected land cells, summing their count. Update the maximum area found. This guarantees linear time relative to the grid size and uses O(m*n) space for the visited set.

What pattern does Max Area of Island use?

The Pattern: DFS (Connected Components in Grid) The Heuristic: When finding connected regions in a grid, use DFS to explore all neighbors recursively, marking visited cells to prevent revisiting and ensure each component is counted exactly once.

Max Area of Island — DFS

Q: What is the time complexity of Max Area of Island?

O(m * n). Each cell is visited at most once during the DFS calls and the outer loops, resulting in linear time proportional to the grid size.

Problem

Given a 2D grid of 0s and 1s, return the size of the largest connected island of 1s, where connectivity is defined as horizontal and vertical adjacency.

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

Example

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 algorithm scans the grid and finds islands by exploring connected 1s. For example, starting at grid[0][2], it finds an island of area 1. Starting at grid[0][7], it explores connected 1s and finds an island of area 6, which is the largest. The DFS recursively visits all connected land cells, marking them visited to avoid double counting.

Approach

Straightforward Solution

A brute-force approach would check every cell and, for each land cell, perform a DFS or BFS to find the connected island size. Without marking visited cells, this would lead to repeated counting and exponential time complexity.

Core Observation

Islands are connected components in a grid graph where edges exist between horizontally or vertically adjacent land cells. The problem reduces to finding the largest connected component size.

Path to Optimal

Preview

The key insight is to track visited cells to avoid revisiting and double counting. By performing a DFS from each unvisited land cell and marking all reachable land cells as visited, the algorithm counts each island exactly once…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use DFS to explore each island starting from unvisited land cells. Maintain a visited set to track explored cells…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(m * n)

Each cell is visited at most once during the DFS calls and the outer loops, resulting in linear time proportional to the grid size.

Space

O(m * n)

The visited set can store up to all cells in the grid in the worst case, and the recursion stack can go as deep as the size of the largest island.

Solution

Python

1class Solution:
  def maxAreaOfIsland(self, grid: list[list[int]]) -> int:
      ROWS, COLS = len(grid), len(grid[0])
      visit = set()
      max_area = 0
6
      def dfs(r, c):
          if (r < 0 or r == ROWS or c < 0 or c == COLS or
                  grid[r][c] == 0 or (r, c) in visit):
              return 0
          
          visit.add((r, c))
          return (1 + dfs(r + 1, c) +
                      dfs(r - 1, c) +
                      dfs(r, c + 1) +
                      dfs(r, c - 1))
17
      for r in range(ROWS):
          for c in range(COLS):
              if grid[r][c] == 1 and (r, c) not in visit:
                  max_area = max(max_area, dfs(r, c))
      
      return max_area

Step-by-Step Solution

1

Track Visited Cells and Initialize Maximum Area

3ROWS, COLS = len(grid), len(grid[0])
4visit = set()
5max_area = 0

Objective

To maintain a record of explored land cells and keep track of the largest island area found so far.

Key Insight

A visited set prevents revisiting cells, which is essential to avoid infinite loops and redundant counting. Initializing max_area to zero sets a baseline for comparison as islands are discovered.

Interview Quick-Check

Core Logic

The visited set ensures each land cell is explored only once, preventing infinite recursion and double counting.

State & Boundaries

Initialize max_area to zero to handle cases where no land exists, ensuring the function returns zero correctly.

2

Recursively Explore Connected Land Cells via DFS

To compute the area of an island by recursively visiting all connected land cells starting from a given cell.

3

Iterate Over Grid to Find and Measure Islands

To scan every cell in the grid and trigger DFS for unvisited land cells, updating the maximum island area found.

4

Return the Largest Island Area Found

To output the maximum area of any island discovered in the grid.

3 more steps with full analysis available on Pro.

Line Analysis

This solution has 3 Critical lines interviewers watch for.

Line 12 Critical

visit.add((r, c))

Mark the current cell as visited before exploring neighbors.

Adding the cell to visited before recursive calls prevents cycles and ensures each land cell is counted exactly once.

Line 8 Critical

if (r < 0 or r == ROWS or c < 0 or c == COLS or

Check if the current cell is out of bounds, water, or already visited.

This base case prevents invalid or redundant exploration, ensuring recursion terminates correctly and only land cells are counted once.

Line 21 Critical

max_area = max(max_area, dfs(r, c))

Update max_area with the larger of current max or the island area found by DFS.

This line maintains the maximum island size found so far, ensuring the final return value is correct.

Full line-by-line criticality + rationale for all 17 lines available on Pro.

Test Your Understanding

Why is it necessary to track visited cells when performing DFS on the grid?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Max Area of Island from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Max Area of Island drill

or drill a free problem

1	`class Solution:`
2	`def maxAreaOfIsland(self, grid: list[list[int]]) -> int:`
3	`ROWS, COLS = len(grid), len(grid[0])`
4	`visit = set()`
5	`max_area = 0`
6
7	`def dfs(r, c):`
8	`if (r < 0 or r == ROWS or c < 0 or c == COLS or`
9	`grid[r][c] == 0 or (r, c) in visit):`
10	`return 0`
11
12	`visit.add((r, c))`
13	`return (1 + dfs(r + 1, c) +`
14	`dfs(r - 1, c) +`
15	`dfs(r, c + 1) +`
16	`dfs(r, c - 1))`
17
18	`for r in range(ROWS):`
19	`for c in range(COLS):`
20	`if grid[r][c] == 1 and (r, c) not in visit:`
21	`max_area = max(max_area, dfs(r, c))`
22
23	`return max_area`