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 - LeetCode Solution

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

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. The maximum size among these counts is the answer. This approach ensures O(m*n) time complexity since each cell is visited at most once.

Optimal Approach

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.

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

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

1import java.util.HashSet;
2import java.util.Set;
3
4public class Solution {
  public int maxAreaOfIsland(int[][] grid) {
      int ROWS = grid.length;
      int COLS = grid[0].length;
      Set<String> visit = new HashSet<>();
      int max_area = 0;
10
      // DFS helper function
      class DFS {
          int dfs(int r, int c) {
              if (r < 0 || r == ROWS || c < 0 || c == COLS || grid[r][c] == 0 || visit.contains(r + "," + c)) {
                  return 0;
              }
              visit.add(r + "," + c);
              return 1 + dfs(r + 1, c) + dfs(r - 1, c) + dfs(r, c + 1) + dfs(r, c - 1);
          }
      }
21
      DFS helper = new DFS();
23
      for (int r = 0; r < ROWS; r++) {
          for (int c = 0; c < COLS; c++) {
              if (grid[r][c] == 1 && !visit.contains(r + "," + c)) {
                  max_area = Math.max(max_area, helper.dfs(r, c));
              }
          }
      }
31
      return max_area;
  }
34}

1#include <vector>
2#include <unordered_set>
3#include <string>
4
5using namespace std;
6
7class Solution {
8public:
9    int maxAreaOfIsland(vector<vector<int>>& grid) {
10        int ROWS = grid.size();
11        int COLS = grid[0].size();
12        unordered_set<string> visit;
13        int max_area = 0;
14
15        function<int(int,int)> dfs = [&](int r, int c) -> int {
16            if (r < 0 || r == ROWS || c < 0 || c == COLS || grid[r][c] == 0 || visit.count(to_string(r) + "," + to_string(c))) {
17                return 0;
18            }
19            visit.insert(to_string(r) + "," + to_string(c));
20            return 1 + dfs(r + 1, c) + dfs(r - 1, c) + dfs(r, c + 1) + dfs(r, c - 1);
21        };
22
23        for (int r = 0; r < ROWS; r++) {
24            for (int c = 0; c < COLS; c++) {
25                if (grid[r][c] == 1 && !visit.count(to_string(r) + "," + to_string(c))) {
26                    max_area = max(max_area, dfs(r, c));
27                }
28            }
29        }
30
31        return max_area;
32    }
33};

1var maxAreaOfIsland = function(grid) {
  const ROWS = grid.length;
  const COLS = grid[0].length;
  const visit = new Set();
  let max_area = 0;
6
  function dfs(r, c) {
      if (r < 0 || r === ROWS || c < 0 || c === COLS || grid[r][c] === 0 || visit.has(r + ',' + c)) {
          return 0;
      }
      visit.add(r + ',' + c);
      return 1 + dfs(r + 1, c) + dfs(r - 1, c) + dfs(r, c + 1) + dfs(r, c - 1);
  }
14
  for (let r = 0; r < ROWS; r++) {
      for (let c = 0; c < COLS; c++) {
          if (grid[r][c] === 1 && !visit.has(r + ',' + c)) {
              max_area = Math.max(max_area, dfs(r, c));
          }
      }
  }
22
  return max_area;
24};

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

7def 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))

Objective

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

Key Insight

DFS explores all neighbors in four directions, summing the count of connected land cells. The base case stops recursion when out of bounds, water, or already visited cells are encountered. Adding the current cell to visited before recursive calls prevents cycles. This approach ensures the entire island is counted exactly once.

Interview Quick-Check

Core Logic

DFS recursively visits all connected land cells, accumulating the island's area while marking cells visited to avoid revisits.

State & Boundaries

The base case checks for out-of-bounds indices, water cells, or previously visited cells to terminate recursion.

Common Pitfalls & Bugs

Failing to mark the current cell as visited before recursive calls can cause infinite recursion or overcounting.

3

Iterate Over Grid to Find and Measure Islands

18for 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))

Objective

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

Key Insight

By iterating over all cells, the algorithm ensures no island is missed. DFS is only called on unvisited land cells, guaranteeing each island is counted once. The max_area variable is updated with the largest island size found so far, ensuring the final result is correct.

Interview Quick-Check

Core Logic

The nested loops ensure every cell is checked, and DFS is triggered only for unvisited land cells to find island sizes.

State & Boundaries

The condition checks both that the cell is land and unvisited before starting DFS.

Complexity

Each cell is visited once, so the nested loops combined with DFS yield O(m*n) time complexity.

4

Return the Largest Island Area Found

23	`return max_area`

Objective

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

Key Insight

After exploring all islands, max_area holds the size of the largest one. Returning it completes the problem's requirement.

Interview Quick-Check

Core Logic

Returning max_area provides the final answer after all islands have been explored.

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.

Line 4 Core

visit = set()

Initialize a set to track visited land cells.

The visited set prevents revisiting cells during DFS, which is essential to avoid infinite recursion and double counting of island cells.

Line 10 Core

return 0

Return zero when the current cell is invalid for exploration.

Returning zero here correctly contributes no area for invalid or already visited cells, maintaining accurate island size counts.

Line 20 Core

if grid[r][c] == 1 and (r, c) not in visit:

Check if the current cell is land and unvisited before DFS.

This condition ensures DFS is only initiated on new islands, preventing redundant exploration.

Line 9 Core

grid[r][c] == 0 or (r, c) in visit):

Continue the compound condition to check invalid DFS entry points.

Combining boundary, water, and visited checks in one condition efficiently guards against invalid recursion paths.

Line 13 Core

return (1 + dfs(r + 1, c) +

Recursively explore the cell below and add its area contribution.

DFS explores all connected land cells by moving down, accumulating the total island area.

Line 14 Core

dfs(r - 1, c) +

Recursively explore the cell above and add its area contribution.

Exploring upward neighbors ensures full vertical connectivity is accounted for in the island area.

Line 15 Core

dfs(r, c + 1) +

Recursively explore the cell to the right and add its area contribution.

Exploring right neighbors completes horizontal connectivity checks for the island.

Line 16 Core

dfs(r, c - 1))

Recursively explore the cell to the left and add its area contribution.

Exploring left neighbors ensures all horizontal connections are included in the island area calculation.

Line 7 Standard

def dfs(r, c):

Define the DFS function to explore connected land cells starting from (r, c).

Encapsulating the recursive exploration logic in a helper function enables clean, reusable traversal of connected components.

Line 23 Standard

return max_area

Return the maximum island area found after full grid traversal.

Returning max_area completes the function by providing the final answer to the problem.

Line 18 Standard

for r in range(ROWS):

Iterate over each row in the grid.

The outer loop ensures every cell in the grid is considered as a potential island starting point.

Line 19 Standard

for c in range(COLS):

Iterate over each column in the current row.

The inner loop completes the full grid traversal, enabling examination of every cell.

Line 5 Standard

max_area = 0

Initialize the variable to track the maximum island area found.

Setting max_area to zero provides a baseline for comparison and handles the case where no land exists in the grid.

Line 3 Basic

ROWS, COLS = len(grid), len(grid[0])

Store the number of rows and columns in the grid.

Caching the grid dimensions simplifies boundary checks and improves code readability by avoiding repeated calls to len().

Test Your Understanding

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

Tracking visited cells prevents revisiting the same land cell multiple times, which avoids infinite recursion and double counting, ensuring each island is counted exactly once.

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`

1	`import java.util.HashSet;`
2	`import java.util.Set;`
3
4	`public class Solution {`
5	`public int maxAreaOfIsland(int[][] grid) {`
6	`int ROWS = grid.length;`
7	`int COLS = grid[0].length;`
8	`Set<String> visit = new HashSet<>();`
9	`int max_area = 0;`
10
11	`// DFS helper function`
12	`class DFS {`
13	`int dfs(int r, int c) {`
14	`if (r < 0 \|\| r == ROWS \|\| c < 0 \|\| c == COLS \|\| grid[r][c] == 0 \|\| visit.contains(r + "," + c)) {`
15	`return 0;`
16	`}`
17	`visit.add(r + "," + c);`
18	`return 1 + dfs(r + 1, c) + dfs(r - 1, c) + dfs(r, c + 1) + dfs(r, c - 1);`
19	`}`
20	`}`
21
22	`DFS helper = new DFS();`
23
24	`for (int r = 0; r < ROWS; r++) {`
25	`for (int c = 0; c < COLS; c++) {`
26	`if (grid[r][c] == 1 && !visit.contains(r + "," + c)) {`
27	`max_area = Math.max(max_area, helper.dfs(r, c));`
28	`}`
29	`}`
30	`}`
31
32	`return max_area;`
33	`}`
34	`}`

1	`#include <vector>`
2	`#include <unordered_set>`
3	`#include <string>`
4
5	`using namespace std;`
6
7	`class Solution {`
8	`public:`
9	`int maxAreaOfIsland(vector<vector<int>>& grid) {`
10	`int ROWS = grid.size();`
11	`int COLS = grid[0].size();`
12	`unordered_set<string> visit;`
13	`int max_area = 0;`
14
15	`function<int(int,int)> dfs = [&](int r, int c) -> int {`
16	`if (r < 0 \|\| r == ROWS \|\| c < 0 \|\| c == COLS \|\| grid[r][c] == 0 \|\| visit.count(to_string(r) + "," + to_string(c))) {`
17	`return 0;`
18	`}`
19	`visit.insert(to_string(r) + "," + to_string(c));`
20	`return 1 + dfs(r + 1, c) + dfs(r - 1, c) + dfs(r, c + 1) + dfs(r, c - 1);`
21	`};`
22
23	`for (int r = 0; r < ROWS; r++) {`
24	`for (int c = 0; c < COLS; c++) {`
25	`if (grid[r][c] == 1 && !visit.count(to_string(r) + "," + to_string(c))) {`
26	`max_area = max(max_area, dfs(r, c));`
27	`}`
28	`}`
29	`}`
30
31	`return max_area;`
32	`}`
33	`};`

1	`var maxAreaOfIsland = function(grid) {`
2	`const ROWS = grid.length;`
3	`const COLS = grid[0].length;`
4	`const visit = new Set();`
5	`let max_area = 0;`
6
7	`function dfs(r, c) {`
8	`if (r < 0 \|\| r === ROWS \|\| c < 0 \|\| c === COLS \|\| grid[r][c] === 0 \|\| visit.has(r + ',' + c)) {`
9	`return 0;`
10	`}`
11	`visit.add(r + ',' + c);`
12	`return 1 + dfs(r + 1, c) + dfs(r - 1, c) + dfs(r, c + 1) + dfs(r, c - 1);`
13	`}`
14
15	`for (let r = 0; r < ROWS; r++) {`
16	`for (let c = 0; c < COLS; c++) {`
17	`if (grid[r][c] === 1 && !visit.has(r + ',' + c)) {`
18	`max_area = Math.max(max_area, dfs(r, c));`
19	`}`
20	`}`
21	`}`
22
23	`return max_area;`
24	`};`

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`
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))`

Problem

Example

Approach

Solution

Step-by-Step Solution

Track Visited Cells and Initialize Maximum Area

Recursively Explore Connected Land Cells via DFS

Iterate Over Grid to Find and Measure Islands

Return the Largest Island Area Found

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.