Max Area of Island

Problem

You are given an m x n binary matrix grid. An island is a group of 1’s (representing land) connected 4-directionally (horizontal or vertical). You may assume all four edges of the grid are surrounded by water.

The area of an island is the number of cells with a value 1 in the island.

Return the maximum area of an island in grid. If there is no island, return 0.

Example 1:

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
Explanation: The answer is not 11, because the island must be connected 4-directionally.

Example 2:

Input: grid = [[0,0,0,0,0,0,0,0]]
Output: 0

Constraints:

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

Solution

Approach: DFS with Area Counting

The key insight is to perform DFS from each unvisited land cell, counting the area while marking cells as visited, then tracking the maximum area found.

Implementation

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        if not grid:
            return 0

        m, n = len(grid), len(grid[0])
        max_area = 0

        def dfs(r, c):
            # Check bounds and if it's water or visited
            if (r < 0 or r >= m or c < 0 or c >= n or
                grid[r][c] == 0):
                return 0

            # Mark as visited
            grid[r][c] = 0

            # Count current cell plus all connected cells
            area = 1
            area += dfs(r + 1, c)
            area += dfs(r - 1, c)
            area += dfs(r, c + 1)
            area += dfs(r, c - 1)

            return area

        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    area = dfs(i, j)
                    max_area = max(max_area, area)

        return max_area

Approach 2: BFS with Area Counting

from collections import deque

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        if not grid:
            return 0

        m, n = len(grid), len(grid[0])
        max_area = 0

        def bfs(r, c):
            queue = deque([(r, c)])
            grid[r][c] = 0
            area = 1

            while queue:
                row, col = queue.popleft()
                directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

                for dr, dc in directions:
                    nr, nc = row + dr, col + dc
                    if (0 <= nr < m and 0 <= nc < n and
                        grid[nr][nc] == 1):
                        grid[nr][nc] = 0
                        queue.append((nr, nc))
                        area += 1

            return area

        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    area = bfs(i, j)
                    max_area = max(max_area, area)

        return max_area

Complexity Analysis

Time Complexity: O(m * n), where m and n are grid dimensions. We visit each cell once.
Space Complexity: O(m * n) in worst case for recursion stack (DFS) or queue (BFS).

Key Insights

Extension of Number of Islands: This is similar to counting islands, but we also track the size of each island.
Accumulating Area: The DFS function returns the total area by summing 1 (current cell) plus areas from all four directions.
In-Place Modification: Marking visited cells by changing 1 to 0 saves space and simplifies the code.
Maximum Tracking: We keep track of the maximum area seen across all islands explored.
Connected Components Size: Each island is a connected component, and we’re finding the size of the largest one.