LeetCode 695: Max Area of Island Solution in Python – A Step-by-Step Guide

What Is LeetCode 695: Max Area of Island?

In LeetCode 695: Max Area of Island, you’re given a 2D binary grid where 1 represents land and 0 represents water, and your task is to find the maximum area of an island. An island is a group of connected 1s (horizontally or vertically), and the area is the number of 1s in that group. Return this maximum area as an integer; if no island exists, return 0. For example, with grid = [[0,0,1,0,0],[0,0,0,0,0],[0,1,1,0,1],[0,0,1,0,0]], the largest island has 4 cells (connected 1s at (2,1), (2,2), (3,2), (1,2)), so return 4. This problem tests your ability to traverse a grid and calculate connected regions efficiently.

Problem Statement

• Input:
• grid: 2D list of integers (0s and 1s).
• Output: An integer—maximum area of an island (number of 1s).
• Rules:
• Island: Connected 1s (4-directional: up, down, left, right).
• Area: Count of 1s in an island.
• Return max area, or 0 if no islands.

Constraints

• 1 ≤ grid.length, grid[0].length ≤ 50.
• grid[i][j] is 0 or 1.

Examples

• Input: grid = [[0,0,1,0,0],[0,0,0,0,0],[0,1,1,0,1],[0,0,1,0,0]]
• Output: 4 (Largest island has 4 cells)
• Input: grid = [[0,0,0],[0,0,0]]
• Output: 0 (No islands)
• Input: grid = [[1,1],[1,1]]
• Output: 4 (One island, 4 cells)

These examples set the grid—let’s solve it!

Understanding the Problem: Measuring Island Areas

To solve LeetCode 695: Max Area of Island in Python, we need to find the maximum area of an island in a grid, where an island is a group of connected 1s, and the area is the count of 1s. A brute-force approach—checking each cell and exploring without optimization—would still be O(n * m) but could be messy with redundant checks. Since we’re traversing connected regions, DFS or BFS can efficiently compute each island’s size by visiting cells once. We’ll use:

• Best Solution (DFS with Grid Modification): O(n * m) time, O(1) extra space—fast and space-efficient.
• Alternative Solution (BFS with Queue): O(n m) time, O(n m) space—intuitive but uses more space.

Let’s start with the DFS solution, breaking it down for beginners.

Best Solution: DFS with Grid Modification

Why This Is the Best Solution

The DFS with grid modification approach is the top choice for LeetCode 695 because it’s highly efficient—O(n * m) time with O(1) extra space (excluding recursion stack)—and uses depth-first search to explore each island, modifying the grid in-place to mark visited cells, avoiding the need for a separate visited set. It fits constraints (n, m ≤ 50) perfectly and is intuitive once you see the recursion logic. It’s like diving into each island and counting cells while painting them as you go!

How It Works

Think of this as an island counter:

• Step 1: Define Directions:
• Moves: [(0, 1), (1, 0), (0, -1), (-1, 0)] (right, down, left, up).
• Step 2: DFS Function:
• Start at a 1, mark as 0 (visited), count 1.
• Recurse on 4 neighbors, sum their areas if 1.
• Step 3: Scan Grid:
• For each cell, if 1, DFS to get island area, track max.
• Step 4: Return Result:
• Maximum area found, or 0 if none.

It’s like a grid painter—count and mark!

Step-by-Step Example

Example: grid = [[0,0,1,0,0],[0,0,0,0,0],[0,1,1,0,1],[0,0,1,0,0]]

• Grid:
``` 0 0 1 0 0 0 0 0 0 0 0 1 1 0 1 0 0 1 0 0 ```
• Step 1: Directions: [(0,1), (1,0), (0,-1), (-1,0)].
• Step 2: DFS:
• Start (0, 2):
• Mark (0, 2) = 0, area = 1.
• No neighbors with 1, return 1.
• Start (2, 1):
• Mark (2, 1) = 0, area = 1.
• Right (2, 2): Mark = 0, area = 1, down (3, 2): Mark = 0, area = 1, left (3, 1): 0, up (2, 1): 0, return 1.
• Down (3, 1): 0, left (2, 0): 0, up (1, 1): 0, return 2.
• Left (1, 0): 0, up (1, 1): 0, return 3.
• Right (2, 2): 0, down (3, 1): 0, return 4.
• Start (2, 4):
• Mark (2, 4) = 0, area = 1, no neighbors, return 1.
• Step 3: Areas: [1, 4, 1], max = 4.
• Step 4: Return 4.
• Output: 4.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codeclass Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        # Step 1: Define directions
        m, n = len(grid), len(grid[0])
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # right, down, left, up

        # Step 2: DFS to compute island area
        def dfs(i: int, j: int) -> int:
            if not (0 <= i < m and 0 <= j < n and grid[i][j] == 1):
                return 0
            grid[i][j] = 0  # Mark visited
            area = 1
            for di, dj in directions:
                area += dfs(i + di, j + dj)
            return area

        # Step 3: Scan grid for islands
        max_area = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    max_area = max(max_area, dfs(i, j))

        # Step 4: Return maximum area
        return max_area

• Lines 4-5: Define: Grid size and 4-directional moves.
• Lines 8-15: DFS:
• Check bounds and value, mark visited, recurse on neighbors.
• Lines 18-23: Scan:
• For each 1, DFS to get area, update max.
• Line 26: Return max_area.
• Time Complexity: O(n * m)—visit each cell once.
• Space Complexity: O(1) extra space (recursion stack O(n * m)).

This is like an island measurer—dive and count!

Alternative Solution: BFS with Queue

Why an Alternative Approach?

The BFS with queue approach uses breadth-first search—O(n * m) time, O(n * m) space. It’s more intuitive for some, exploring islands level-by-level with a queue, but requires extra space for the queue and visited set. It’s like fanning out across each island to count its cells!

How It Works

Picture this as an island spreader:

• Step 1: Define directions.
• Step 2: BFS Function:
• Queue starting cell, mark visited, count 1.
• Process neighbors, enqueue unvisited 1s.
• Step 3: Scan grid:
• BFS on each unvisited 1, track max area.
• Step 4: Return max area.

It’s like a queue counter—spread and tally!

Step-by-Step Example

Example: Same as above

• Step 1: Directions defined.
• Step 2: BFS:
• Start (0, 2): Queue = [(0, 2)], area = 1, mark visited, no neighbors, return 1.
• Start (2, 1): Queue = [(2, 1)], area = 1, mark.
• (2, 2): Queue = [(2, 2)], area = 2, mark.
• (3, 2): Queue = [(3, 2)], area = 3, mark.
• (1, 1): Queue = [(1, 1)], area = 4, mark.
• Queue empty, return 4.
• Start (2, 4): Queue = [(2, 4)], area = 1, return 1.
• Step 3: Areas: [1, 4, 1], max = 4.
• Step 4: Return 4.
• Output: 4.

Code for BFS Approach

Copy codefrom collections import deque

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]

        # Step 1: BFS to compute island area
        def bfs(i: int, j: int) -> int:
            queue = deque([(i, j)])
            area = 0
            while queue:
                r, c = queue.popleft()
                if not (0 <= r < m and 0 <= c < n and grid[r][c] == 1):
                    continue
                grid[r][c] = 0  # Mark visited
                area += 1
                for dr, dc in directions:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:
                        queue.append((nr, nc))
            return area

        # Step 2: Scan grid
        max_area = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    max_area = max(max_area, bfs(i, j))

        # Step 3: Return max area
        return max_area

• Line 1: Import deque.
• Lines 5-6: Define directions.
• Lines 9-22: BFS:
• Queue cells, mark visited, count area, enqueue neighbors.
• Lines 25-30: Scan:
• BFS on each 1, update max_area.
• Line 33: Return max_area.
• Time Complexity: O(n * m)—visit each cell once.
• Space Complexity: O(n * m)—queue size.

It’s a spread measurer—queue and count!

Comparing the Two Solutions

• DFS (Best):
• Pros: O(n * m) time, O(1) extra space, efficient and simple.
• Cons: Recursion less obvious.
• BFS (Alternative):
• Pros: O(n m) time, O(n m) space, clear level-wise.
• Cons: More space, queue overhead.

DFS wins for space efficiency.

Additional Examples and Edge Cases

• Input: grid = [[1]]
• Output: 1.
• Input: grid = [[0]]
• Output: 0.

DFS handles these well.

Complexity Breakdown

• DFS: Time O(n m), Space O(1) extra (O(n m) with stack).
• BFS: Time O(n m), Space O(n m).

DFS is optimal for space.

Key Takeaways

• DFS: Depth counting—smart!
• BFS: Breadth spreading—clear!
• Islands: Measuring is fun.
• Python Tip: DFS rocks—see Python Basics.

Final Thoughts: Survey That Island

LeetCode 695: Max Area of Island in Python is a fun grid challenge. DFS with grid modification offers speed and elegance, while BFS with queue provides a clear alternative. Want more? Try LeetCode 200: Number of Islands or LeetCode 463: Island Perimeter. Ready to measure? Head to Solve LeetCode 695 on LeetCode and find that max area today!