We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Max Area of Island

Difficulty: Medium

Problem Description

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.

Key Insights

  • An island is identified by connected components of 1's in the grid.
  • We can use Depth-First Search (DFS) or Breadth-First Search (BFS) to explore each island.
  • We need to keep track of the maximum area encountered during our exploration.
  • The grid is bounded, so we will not go out of bounds during our search.

Space and Time Complexity

Time Complexity: O(m * n)
Space Complexity: O(m * n) in the worst case due to the recursion stack or queue storage for DFS/BFS.

Solution

To solve the problem, we can use either a Depth-First Search (DFS) or a Breadth-First Search (BFS) approach. We will iterate through each cell in the grid. When we encounter a cell with a value of 1, we will initiate a search to explore the entire island connected to that cell, counting the number of 1's encountered. We will track the maximum area of any island found during these searches. We will mark cells as visited by changing their value to 0 to avoid counting them multiple times.

Code Solutions

def maxAreaOfIsland(grid):
    if not grid:
        return 0

    max_area = 0
    rows, cols = len(grid), len(grid[0])

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == 0:
            return 0
        grid[r][c] = 0  # Mark as visited
        area = 1  # Count the current cell
        # Explore all four directions
        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(rows):
        for j in range(cols):
            if grid[i][j] == 1:
                max_area = max(max_area, dfs(i, j))

    return max_area
← Back to All Questions