Domain 2MediumMEDIUM

Max Area of Island

LeetCode problem 695: Max Area of Island (medium).

Domain: medium•Updated: 2026-08-30
#Array#Depth-first Search

Problem Breakdown

We are given a 2D grid representing land (1) and water (0). An island is defined as any group of 1s connected horizontally or vertically (4-directional). Our goal is to find the maximum area among all islands. The “area” corresponds to the count of cells in that specific island component.

Inputs:

  • A 2D list of integers (grid), where values are either 0 or 1.
  • Dimensions up to 50×5050 \times 50.

Outputs:

  • An integer representing the maximum area found. Returns 0 if no islands exist (all water).

Implicit Constraints & Edge Cases:

  • Connectivity: Only orthogonal neighbors count; diagonal connections do not form an island.
  • Visited State: Once a cell is counted as part of an island, it cannot be reused for another area calculation to avoid double-counting within the same traversal or across different islands if we don’t mark them visited.
  • Empty/All Water Grids: Must return 0.
  • Grid Boundaries: We must ensure neighbor checks do not go out of bounds (row index <0< 0 or ≥R\ge R, col index <0< 0 or ≥C\ge C).

Intuition

A naive approach might be to iterate through every cell. If we find a 1, we count it and its neighbors recursively until the island ends, then reset counters for other islands. However, if we don’t mark cells as visited during this process, we will re-count the same land mass multiple times when our outer loop encounters different parts of that same island later on.

Brute Force Complexity: If we simply count connected components without marking visited nodes (e.g., using a visited set), or if we iterate through every cell and run BFS/DFS from every unvisited land cell, the complexity becomes O((R×C)2)O((R \times C)^2) in worst-case scenarios where many islands overlap conceptually but are distinct. More simply, without marking visited cells as water (0) during traversal, we risk exponential time due to redundant traversals of the same component.

Key Insight: We need a “visited” mechanism. Since modifying the input grid is allowed and saves space (we don’t need it later), we can turn 1s into 0s once they are visited. This effectively marks them as processed water, preventing us from counting them again in future iterations of our outer loop or within the same DFS traversal.

Approach

  1. Initialize a variable max_area to store the largest island found so far (default 0).
  2. Iterate through every cell (row, col) in the grid using nested loops.
  3. If we encounter a land cell (grid[row][col] == 1):
    • This is part of an unexplored island. Start a Depth-First Search (DFS) from this position to calculate its total area.
    • During DFS, increment the current island’s counter for every valid neighbor that is also land (1).
    • Crucially, mark visited cells as water (0) immediately upon visiting them so they aren’t counted again in future steps or by other branches of the same traversal.
  4. Update max_area with the result from this specific island’s DFS if it exceeds the current maximum.
  5. Continue until all grid cells are checked. Return max_area.

Complexity Analysis

  • Time Complexity: O(R×C)O(R \times C), where RR is rows and CC is columns. We visit each cell at most twice: once in the outer loop check and potentially once during a DFS traversal (where we mark it visited). Since every 1 becomes 0, no land cell triggers multiple full traversals.
  • Space Complexity: O(1)O(1) auxiliary space if we modify the input grid to track visited status, excluding recursion stack overhead. If considering Python’s call stack for recursive DFS in a snake-like island pattern, it is technically O(min⁡(R,C))O(\min(R, C)) due to the maximum depth of the recursion tree being bounded by the longest path (though typically limited by max⁡(N)\max(N)). Given constraints (50×5050 \times 50), this fits well within standard limits.

Solution

class Solution:
    def maxAreaOfIsland(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        
        if not grid or not grid[0]:
            return 0
            
        rows = len(grid)
        cols = len(grid[0])
        max_area = 0
        
        def dfs(r, c):
            # Base cases for recursion boundaries and water cells
            if r < 0 or r >= rows or c < 0 or c >= cols:
                return 0
            
            # If current cell is land (1), process it. 
            # Mark as visited by setting to 0 immediately to avoid double counting.
            grid[r][c] = 0 
            
            area = 1 + dfs(r - 1, c) + \
                    dfs(r + 1, c) + \
                    dfs(r, c - 1) + \
                    dfs(r, c + 1)
            
            return area
        
        # Iterate over every cell in the grid
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 1:
                    current_area = dfs(r, c)
                    max_area = max(max_area, current_area)
                    
        return max_area

Edge Cases Handled

  • All Water Grid: The outer loop finds no 1s; returns initial max_area of 0. Correct.
  • Single Island vs Multiple Islands: DFS naturally isolates components because we mark cells as visited (0). Once an island is fully traversed, subsequent iterations in the main loops skip its remaining parts (now marked water).
  • Boundary Conditions: The recursive function checks indices against rows and cols before accessing neighbors. This prevents index out of bounds errors on edges or corners.
  • Recursion Depth: While Python has a recursion limit, for 50×5050 \times 50 grids the maximum depth is manageable within standard limits (typically ~1000), though iterative DFS would be used in production systems requiring strict memory safety against deep snake-like paths.