Max Area of Island

Problem Statement

You are given a matrix grid where grid[i] is either a 0 (representing water) or 1 (representing land).

An island is defined as a group of 1’s connected horizontally or vertically. You may assume all four edges of the grid are surrounded by water.

The area of an island is defined as the number of cells within the island.

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

Example 1:

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


Output: 6

Explanation: 1’s cannot be connected diagonally, so the maximum area of the island is 6.

Constraints:

  • 1 <= grid.length, grid[i].length <= 50

You should aim for a solution with O(m * n) time and O(m * n) space, where m is the number of rows and n is the number of columns in the grid.

You should aim for a solution with O(m * n) time and O(m * n) space, where m is the number of rows and n is the number of columns in the grid.

Hint 1

An island is a group of 1’s in which every 1 is reachable from any other 1 in that group. Can you think of an algorithm that can find the number of groups by visiting a group only once? Maybe there is a recursive way of doing it.

Hint 2

We can use the Depth First Search (DFS) algorithm to traverse each group by starting at a cell with 1 and recursively visiting all the cells that are reachable from that cell and are also 1. Can you think about how to find the area of that island? How would you implement this?

Hint 3

We traverse the grid, and when we encounter a 1, we initialize a variable area. We then start a DFS from that cell to visit all connected 1’s recursively, marking them as 0 to indicate they are visited. At each recursion step, we increment area. After completing the DFS, we update maxArea, which tracks the maximum area of an island in the grid, if maxArea < area. Finally, after traversing the grid, we return maxArea.

Solution

def max_area_of_island(grid: List[List[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    visited = set()


    def dfs(row, col):
        if (row < 0 or row == rows or col < 0 or
            col == cols or grid[row][col] == 0 or
            (row, col) in visited):
            return 0


        visited.add((row, col))
        return (1 + dfs(row + 1, col) +
                    dfs(row - 1, col) +
                    dfs(row, col + 1) +
                    dfs(row, col - 1))


    area = 0
    for row in range(rows):
        for col in range(cols):
            area = max(area, dfs(row, col))
    return area

Time complexity: O(m * n) Space complexity: O(m * n)