LeetCode 695 - Max Area of Island

The problem is asking us to find the largest connected area of land in a 2D binary matrix. Each cell in the matrix represents either water (0) or land (1). A group of 1s forms an island if the 1s are connected 4-directionally (up, down, left, or right).

leetcodemediumarraydepth-first-searchbreadth-first-searchunion-findmatrix

LeetCode Problem 695

Difficulty: 🟡 Medium
Topics: Array, Depth-First Search, Breadth-First Search, Union-Find, Matrix

Solution

Problem Understanding

The problem is asking us to find the largest connected area of land in a 2D binary matrix. Each cell in the matrix represents either water (0) or land (1). A group of 1s forms an island if the 1s are connected 4-directionally (up, down, left, or right). Diagonal connections do not count. The task is to traverse the entire grid, identify all islands, calculate their areas, and return the maximum area found. If no land exists in the grid, we return 0.

The input is a 2D list grid with dimensions m x n, where 1 <= m, n <= 50. This constraint tells us the grid is relatively small, so an algorithm with time complexity up to O(m * n) is acceptable. The grid values are guaranteed to be either 0 or 1, so we do not need to validate input values.

Edge cases include grids with no land at all, a grid that is a single row or column, or multiple small islands of equal size. The problem guarantees that all grid edges are surrounded by water, simplifying boundary checks.

Approaches

A brute-force approach would iterate over every cell in the grid. Whenever a 1 is found, we could recursively or iteratively explore all connected land cells using DFS or BFS, counting the size of that island. Each visited cell would need to be marked to avoid double-counting. This approach is correct because it systematically explores each island, but it may revisit cells multiple times in less efficient implementations, making it slower. For the constraints given, this is still feasible, but we can optimize it by marking visited cells immediately.

The key insight for an optimal solution is to use DFS or BFS with marking of visited cells. By converting each visited land cell to 0 (water), we avoid revisiting it. This allows a single traversal of each land cell exactly once, which reduces unnecessary repeated work. DFS is often preferred for simplicity and stack-based recursion, while BFS is iterative with a queue.

Approach Time Complexity Space Complexity Notes
Brute Force O((m * n) * k) O(m * n) Explore every land cell, but may revisit parts of islands multiple times
Optimal (DFS/BFS) O(m * n) O(m * n) Each land cell is visited exactly once, marking cells prevents revisits

Algorithm Walkthrough

  1. Initialize a variable max_area to 0 to track the largest island found.
  2. Iterate over each cell (i, j) in the grid.
  3. When a cell with value 1 is found, start a DFS or BFS from that cell to explore the entire island.
  4. During exploration, for every land cell visited, mark it as 0 to indicate it has been counted. This prevents double-counting.
  5. Count the total number of cells visited during this exploration. This gives the area of the current island.
  6. Update max_area if the current island's area is larger than the previous maximum.
  7. Continue iterating through the grid until all cells are processed.
  8. Return max_area as the result.

Why it works: The invariant is that every land cell is visited exactly once. By marking visited cells as water, the algorithm guarantees that each island is counted precisely once. Since we explore all directions recursively or iteratively, no connected land is missed, and the maximum area is tracked throughout.

Python Solution

from typing import List

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        def dfs(i: int, j: int) -> int:
            if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == 0:
                return 0
            grid[i][j] = 0  # mark visited
            area = 1
            area += dfs(i + 1, j)
            area += dfs(i - 1, j)
            area += dfs(i, j + 1)
            area += dfs(i, j - 1)
            return area
        
        max_area = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    max_area = max(max_area, dfs(i, j))
        return max_area

The Python implementation uses a helper DFS function to explore islands recursively. Each recursive call checks boundary conditions and whether the cell is water. The DFS function sums the area of all connected land cells. During the main iteration, we update max_area whenever a new island area is calculated.

Go Solution

func maxAreaOfIsland(grid [][]int) int {
    var dfs func(i, j int) int
    dfs = func(i, j int) int {
        if i < 0 || i >= len(grid) || j < 0 || j >= len(grid[0]) || grid[i][j] == 0 {
            return 0
        }
        grid[i][j] = 0
        area := 1
        area += dfs(i+1, j)
        area += dfs(i-1, j)
        area += dfs(i, j+1)
        area += dfs(i, j-1)
        return area
    }

    maxArea := 0
    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[0]); j++ {
            if grid[i][j] == 1 {
                maxArea = max(maxArea, dfs(i, j))
            }
        }
    }
    return maxArea
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

The Go implementation mirrors the Python version. Recursive DFS is defined using an inner function closure. Go requires an explicit max helper because the standard library does not provide a generic function. Slice indexing and boundary checking are similar to Python, but Go requires integer handling explicitly.

Worked Examples

Example 1:

Grid state during the first DFS call at (0, 2):

Step DFS Position Cells Marked Current Area max_area
1 (0,2) (0,2) 1 1
2 (1,2) (1,2) 2 2
3 (2,2) (2,2) 3 3
4 (2,1) (2,1) 4 4
5 (3,1) (3,1) 5 5
6 (4,1) (4,1) 6 6

After finishing the DFS, max_area is updated to 6. Other islands are smaller, so final output is 6.

Example 2:

Grid is all zeros. No DFS calls are made. max_area remains 0.

Complexity Analysis

Measure Complexity Explanation
Time O(m * n) Each cell is visited once. DFS does not revisit marked cells.
Space O(m * n) Stack space for recursion in worst-case a large island spanning the entire grid.

The algorithm is efficient for the given constraints because the maximum grid size is 50x50 = 2500 cells. Even in the worst-case, recursion depth is limited to the number of land cells.

Test Cases

# provided examples
assert Solution().maxAreaOfIsland([[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]]) == 6  # multiple islands
assert Solution().maxAreaOfIsland([[0,0,0,0,0,0,0,0]]) == 0  # all water

# boundary tests
assert Solution().maxAreaOfIsland([[1]]) == 1  # single cell island
assert Solution().maxAreaOfIsland([[0]]) == 0  # single cell water
assert Solution().maxAreaOfIsland([[1,1,1,1,1]]) == 5  # single row island
assert Solution().maxAreaOfIsland([[1],[1],[1]]) == 3  # single column island

# stress test
assert Solution().maxAreaOfIsland([[1]*50 for _