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

Code

from collections import deque

VISITED = -1


def maxAreaOfIsland(grid: list[list[int]]) -> int:
    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

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