Max Area of Island

Problem

https://leetcode.com/problems/max-area-of-island/

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.

Pattern

Array, Depth-First Search, Breadth-First Search, Union-Find, Matrix

Approaches

BFS

Explanation

Starting from any land cell, we can use BFS to visit all other connected land cells, incrementing area by 1 each time. Along the way, we mark any land cell we visit as VISITED = -1 to avoid revisiting cells.

Code

from collections import deque

VISITED = -1


def maxAreaOfIsland(grid: list[list[int]]) -> int:
    """Return the maximum area of an island in ``grid``, or ``0`` if there is
    none.
    """
    M = len(grid)
    N = len(grid[0])

    def bfs(start_i, start_j):
        area = 0

        queue = deque()
        queue.append((start_i, start_j))

        while queue:
            i, j = queue.popleft()

            if not (0 <= i < M and 0 <= j < N):
                continue

            if grid[i][j] == VISITED or grid[i][j] == 0:
                continue

            if grid[i][j] == 1:
                grid[i][j] = VISITED
                area += 1

                queue.append((i + 1, j))
                queue.append((i - 1, j))
                queue.append((i, j + 1))
                queue.append((i, j - 1))

        return area

    result = 0
    for i in range(M):
        for j in range(N):
            if grid[i][j] == 1:
                result = max(bfs(i, j), result)

    return result

Test

>>> from max_area_of_island__bfs import maxAreaOfIsland
>>> 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
>>> maxAreaOfIsland([[0,0,0,0,0,0,0,0]])
0

Complexity

Measure	Complexity	Notes
Time	\(O(mn)\)	worst case entire grid is one island so we visit every cell
Auxiliary Space	\(O(m + n)\)	worst case entire grid is one island; the maximum size of the queue will be the diagonal of the grid (\(\sqrt{m^2 + n^2} \leq m + n\))

max_area_of_island__bfs.maxAreaOfIsland(grid: list[list[int]]) → int

Return the maximum area of an island in grid, or 0 if there is none.