Problem Description

You have a 2D binary grid (matrix) where each cell contains either a 0 or a 1. The 1s represent land and 0s represent water.

An island is formed by connecting adjacent 1s (land cells) horizontally or vertically (4-directional connectivity). Diagonal connections don't count. The entire grid is surrounded by water on all four edges.

The area of an island is simply the count of 1s that form that island.

Your task is to find the largest island in the grid and return its area. If the grid contains no islands (all cells are 0), return 0.

For example, if you have a grid like:

[[1,1,0,0,0],
 [1,1,0,0,0],
 [0,0,1,0,0],
 [0,0,0,1,1]]

There are three islands:

• Top-left island with 4 connected 1s (area = 4)
• Middle island with 1 cell (area = 1)
• Bottom-right island with 2 connected 1s (area = 2)

The maximum area among all islands is 4, so you would return 4.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The 2D grid can be viewed as a graph where each cell is a node. Adjacent cells (horizontally and vertically) with value 1 form edges between nodes. Islands are essentially connected components in this graph.

Is it a tree?

• No: The problem involves finding connected components (islands) in a grid, which can have multiple disconnected parts and doesn't follow a tree structure.

Is the problem related to directed acyclic graphs?

• No: The grid represents an undirected graph where connections between land cells are bidirectional.

Is the problem related to shortest paths?

• No: We're not looking for shortest paths between points. We need to find the size of connected components (islands).

Does the problem involve connectivity?

• Yes: The core of the problem is identifying connected components (islands) of 1s and finding their sizes.

Does the problem have small constraints?

• Yes: The grid dimensions are typically manageable (m × n grid), allowing us to visit each cell and explore islands.

DFS/backtracking?

• Yes: DFS is perfect for exploring each island completely. When we find a 1, we can use DFS to visit all connected 1s, counting them to get the island's area.

Conclusion: The flowchart suggests using DFS (Depth-First Search) to explore each island and calculate its area. We iterate through the grid, and whenever we find an unvisited land cell (1), we perform DFS to explore the entire island while counting its cells.

Intuition

Think of the grid as a map where you're looking at islands from above. To find the largest island, you need to explore each island completely and measure its size.

The key insight is that once you land on any part of an island (a cell with 1), you want to explore the entire island to count all its land cells. This is where DFS comes in naturally - when you find a 1, you recursively explore all its adjacent 1s in four directions (up, down, left, right).

Here's the thought process:

1. Starting Point: Scan through the entire grid. Whenever you encounter a 1, it could be part of an unexplored island.

2. Island Exploration: Once you find a 1, you need to count how many connected 1s form this island. DFS is perfect here because:

   • From the current 1, you check all 4 adjacent cells
   • If an adjacent cell is also 1, it's part of the same island, so you continue exploring from there
   • This recursive exploration naturally covers the entire island

3. Avoiding Recounting: A clever trick is to mark visited cells by changing 1s to 0s as we explore. This serves two purposes:

   • Prevents infinite loops (visiting the same cell repeatedly)
   • Ensures each land cell is counted only once

4. Finding Maximum: As we explore each island and get its area, we keep track of the maximum area found so far.

The beauty of this approach is its simplicity - we're essentially doing a flood-fill operation (like the paint bucket tool in image editors) on each island, counting cells as we go. The DFS naturally handles the irregular shapes of islands and ensures we explore every connected piece of land.

The formula for each island's area is straightforward: start with 1 for the current cell, then add the areas returned by DFS calls to all valid adjacent land cells. The recursion stops when we hit water (0) or grid boundaries.

Learn more about Depth-First Search, Breadth-First Search and Union Find patterns.

Solution Approach

The implementation uses DFS with in-place modification to efficiently find the maximum island area:

Main Function Structure:

def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
    m, n = len(grid), len(grid[0])
    return max(dfs(i, j) for i in range(m) for j in range(n))

The main function iterates through every cell in the grid and calls DFS on each position. It returns the maximum area found across all DFS calls.

DFS Helper Function:

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

Key Implementation Details:

1. Base Case: If the current cell is water (grid[i][j] == 0), return 0 immediately. This handles both actual water cells and already-visited land cells.

2. Marking Visited: The line grid[i][j] = 0 marks the current land cell as visited by converting it to water. This prevents revisiting the same cell and avoids infinite recursion.

3. Area Counting: Start with ans = 1 to count the current cell, then add the areas of all connected land cells.

4. Direction Traversal: The clever use of dirs = (-1, 0, 1, 0, -1) with pairwise generates the four directions:

   • pairwise(dirs) produces: (-1, 0), (0, 1), (1, 0), (0, -1)
   • These represent movements: up, right, down, left

5. Boundary Checking: Before making recursive calls, check if the new coordinates (x, y) are within grid boundaries: 0 <= x < m and 0 <= y < n.

6. Recursive Accumulation: For each valid adjacent cell, add its DFS result to the current area: ans += dfs(x, y). If it's water or out of bounds, the DFS returns 0.

Time Complexity: O(m × n) where m and n are the grid dimensions. Each cell is visited at most once.

Space Complexity: O(m × n) in the worst case for the recursion stack when the entire grid is one island.

The elegance of this solution lies in its simplicity - by modifying the grid in-place and using DFS to explore each island completely, we avoid the need for additional visited arrays or complex state management.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach:

Grid:
[[1, 1, 0],
 [0, 1, 0],
 [1, 0, 1]]

Step 1: Start scanning from position (0,0)

• We find a 1 at (0,0), so we start DFS
• Mark (0,0) as visited by setting it to 0
• Current area = 1
• Check 4 directions:
  • Up: Out of bounds
  • Right: (0,1) has 1, recursively call DFS
  • Down: (1,0) has 0, skip
  • Left: Out of bounds

Step 2: DFS from (0,1)

• Mark (0,1) as 0
• Current area = 1
• Check 4 directions:
  • Up: Out of bounds
  • Right: (0,2) has 0, skip
  • Down: (1,1) has 1, recursively call DFS
  • Left: (0,0) now has 0 (already visited), skip

Step 3: DFS from (1,1)

• Mark (1,1) as 0
• Current area = 1
• Check 4 directions:
  • Up: (0,1) now has 0 (already visited), skip
  • Right: (1,2) has 0, skip
  • Down: (2,1) has 0, skip
  • Left: (1,0) has 0, skip
• Return 1 to Step 2

Step 4: Complete DFS from (0,1)

• Total area from (1,1) = 1
• Return 1 + 1 = 2 to Step 1

Step 5: Complete DFS from (0,0)

• Total area from (0,1) = 2
• Return 1 + 2 = 3

First island complete with area = 3

Grid now looks like:

[[0, 0, 0],
 [0, 0, 0],
 [1, 0, 1]]

Step 6: Continue scanning

• Positions (0,1) through (1,2) all have 0, DFS returns 0
• Position (2,0) has 1, start new DFS
  • Mark as 0, check all directions
  • All neighbors are 0 or out of bounds
  • Return area = 1

Step 7: Continue to (2,2)

• Position (2,2) has 1, start new DFS
  • Mark as 0, check all directions
  • All neighbors are 0 or out of bounds
  • Return area = 1

Step 8: Find maximum

• Island areas found: 3, 1, 1
• Maximum area = 3

The grid is completely processed, and we return 3 as the maximum island area.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m * n) where m is the number of rows and n is the number of columns in the grid.

• The main function iterates through every cell in the grid using the generator expression, which takes O(m * n) time.
• For each cell, if it contains a 1, the DFS function is called.
• The DFS function visits each cell at most once because:
  • When a cell with value 1 is visited, it's immediately marked as 0 (visited)
  • Cells with value 0 return immediately without further recursion
• Each cell is processed exactly once across all DFS calls combined
• The pairwise(dirs) operation generates 4 direction pairs, which is O(1)
• Therefore, the total time complexity is O(m * n)

Space Complexity: O(m * n) in the worst case.

• The space complexity is dominated by the recursion call stack
• In the worst case, when the entire grid forms a single island (all cells are 1), the DFS recursion depth could reach O(m * n)
• This happens when the island forms a snake-like pattern that requires deep recursion
• The dirs tuple and other local variables use O(1) space
• The generator expression in the main function uses O(1) additional space
• Therefore, the overall space complexity is O(m * n) due to the recursion stack

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Modifying the Original Grid

The most significant pitfall in this solution is that it modifies the input grid in-place by setting visited cells to 0. This destructive modification means:

• The original grid data is lost after running the function
• The function cannot be called multiple times on the same grid
• This violates the principle of not modifying input parameters unless explicitly required

Solution: Create a copy of the grid or use a separate visited set to track visited cells:

def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    visited = set()
  
    def dfs(row: int, col: int) -> int:
        if (row, col) in visited or grid[row][col] == 0:
            return 0
      
        visited.add((row, col))
        area = 1
      
        for dr, dc in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
            next_row, next_col = row + dr, col + dc
            if 0 <= next_row < rows and 0 <= next_col < cols:
                area += dfs(next_row, next_col)
      
        return area
  
    max_area = 0
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == 1 and (i, j) not in visited:
                max_area = max(max_area, dfs(i, j))
  
    return max_area

2. Missing pairwise Import

The code uses pairwise without importing it. This function is only available in Python 3.10+ from itertools.

Solution: Either import it or use a simpler direction list:

from itertools import pairwise  # Add this import

# Or replace the direction logic with:
directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
for delta_row, delta_col in directions:
    # ... rest of the code

3. Inefficient Maximum Calculation

The current approach calls DFS on every cell, including water cells (0s) and already-visited land cells, which immediately return 0. This creates unnecessary function calls.

Solution: Check if a cell is worth exploring before calling DFS:

def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    max_area = 0
  
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == 1:  # Only call DFS on unvisited land
                max_area = max(max_area, dfs(i, j))
  
    return max_area

4. Stack Overflow Risk

For very large islands, the recursive DFS approach could cause stack overflow due to deep recursion.

Solution: Use an iterative approach with an explicit stack:

def dfs_iterative(row: int, col: int) -> int:
    if grid[row][col] == 0:
        return 0
  
    stack = [(row, col)]
    area = 0
  
    while stack:
        r, c = stack.pop()
        if grid[r][c] == 0:
            continue
          
        grid[r][c] = 0
        area += 1
      
        for dr, dc in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                stack.append((nr, nc))
  
    return area