LeetCode 695: Max Area Of Island — Step-by-Step Visual Trace

#leetcode #python #algorithms

Medium — Depth-First Search | Grid Traversal | Matrix | Recursion

The Problem

Find the maximum area of an island in a 2D binary grid where 1 represents land and 0 represents water. An island is formed by connecting adjacent lands horizontally or vertically.

Approach

Use depth-first search (DFS) to explore each island when encountering a land cell. For each cell, recursively explore all four directions and count connected land cells. Mark visited cells as 0 to avoid revisiting and track the maximum area found.

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

Code

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        def dfs(row, col):
            if (
                row < 0
                or row >= len(grid)
                or col < 0
                or col >= len(grid[0])
                or grid[row][col] == 0
            ):
                return 0

            grid[row][col] = 0  # Mark as visited
            area = 1

            area += dfs(row + 1, col)  # Check down
            area += dfs(row - 1, col)  # Check up
            area += dfs(row, col + 1)  # Check right
            area += dfs(row, col - 1)  # Check left

            return area

        max_area = 0
        for row in range(len(grid)):
            for col in range(len(grid[0])):
                if grid[row][col] == 1:
                    max_area = max(max_area, dfs(row, col))

        return max_area