loading

Max Area of Island — Step-by-Step Visualization

mediumLeetCode #695ArrayDFSBFSUnion FindMatrix

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 value `1` in the island. Return the maximum area of an island in the grid. If or there is no island, return 0.

Algorithm Pattern

Flood Fill (DFS/BFS) with Summation

Key Idea

Similar to 'Number of Islands', we iterate through the grid. When we hit land (`1`), we start a DFS to find the area of the entire connected island. The DFS function returns the sum of all reachable `1`s (1 + DFS of neighbors). We track the maximum value returned by these DFS calls.

Step-by-Step Approach

  1. Initialize `maxArea = 0`.
  2. Loop through every cell `grid[r][c]`.
  3. If cell is land (`1`):
  4. Calculate `area = DFS(r, c)`.
  5. Update `maxArea = max(maxArea, area)`.
  6. In DFS: Mark current cell as visited, return 1 + sum of DFS on 4 neighbors.

Common Gotchas

  • Make sure cells are marked as visited (or changed to `0`) so they aren't counted multiple times.
  • Handle grid boundaries correctly.

Related Problems

← All problems