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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Max Area of Island

Number: 695

Difficulty: Medium

Paid? No

Companies: Meta, Google, LinkedIn, TikTok, Microsoft, Bloomberg, Amazon, DoorDash, Uber, Dropbox, Salesforce, Goldman Sachs, Snowflake, Smartsheet, Tesla, Intuit

Problem Description

Given an m x n binary matrix grid, an island is defined as a group of adjacent 1’s (land) connected 4-directionally (up, down, left, right). The goal is to find the maximum area of an island in the grid where the area is the total number of 1’s in that island. If no island exists, return 0.

Key Insights

  • Traverse each cell in the grid.
  • Use Depth-First Search (DFS) or Breadth-First Search (BFS) to explore connected 1’s.
  • Mark visited cells to prevent double counting (e.g., by setting them to 0).
  • Maintain and update a maximum area count during traversal.
  • The grid's boundaries are naturally water, so no extra edge processing is needed.

Space and Time Complexity

Time Complexity: O(m * n) where m and n are the dimensions of the grid since every cell is visited at most once. Space Complexity: O(m * n) in the worst-case scenario for the recursion stack (or auxiliary data structures) when the grid is entirely land.

Solution

The solution leverages a DFS approach to iterate over each cell in the given grid. When a cell with a value of 1 is encountered, a DFS is initiated from that cell to calculate the area of the island connected to it. Cells are marked as visited (by changing them from 1 to 0) during the DFS to avoid revisiting. The DFS explores all four directions (up, down, left, right) and accumulates the count of connected cells. The maximum area found among all islands is returned at the end. This approach efficiently computes the largest island area with a simple traversal mechanism.

Code Solutions

# Function to compute the maximum area of an island in a grid using DFS
def maxAreaOfIsland(grid):
    # Determine the dimensions of the grid
    rows = len(grid)
    cols = len(grid[0]) if rows else 0

    # Helper function for performing DFS on the grid
    def dfs(r, c):
        # Check if the current cell is out-of-bounds or is water
        if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] == 0:
            return 0
        # Mark the current cell as visited by setting it to 0 (water)
        grid[r][c] = 0
        area = 1  # Count the current cell as part of the island
        # Recursively 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

    max_area = 0
    # Iterate through each cell in the grid
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                # Update max_area with the area obtained from the DFS
                max_area = max(max_area, dfs(r, c))
    return max_area
← Back to All Questions