Max Area of Island

Explanation & Solution

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.

Input: grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]

Output: 6

Explanation: The largest island has area 6 (the group of 1's in the bottom-right region).

Constraints

m == grid.length
n == grid[i].length
1 <= m, n <= 50
grid[i][j] is either 0 or 1

Approach

Graphs pattern

1. Initialize Variables

Get the number of rows and cols from the grid
Set maxArea = 0 to track the largest island found

2. Define DFS Helper

Create a dfs(r, c) function that:
Returns 0 if out of bounds or the cell is water (0)
Marks the current cell as visited by setting grid[r][c] = 0
Returns 1 + sum of DFS on all 4 neighbors

3. Iterate Over Every Cell

Loop through each cell (r, c) in the grid
If grid[r][c] === 1, it's an unvisited land cell
Call dfs(r, c) to compute the area of the island starting from that cell

4. Track Maximum Area

After each DFS call, update maxArea with Math.max(maxArea, area)
The DFS returns the total count of connected land cells for that island

5. Return Result

After scanning all cells, return maxArea
If no island was found, maxArea remains 0

Key Insight

We use DFS to flood-fill each island, marking cells as visited by setting them to 0
Each DFS call returns the area of the connected component it explores

Time

O(m × n)each cell is visited at most once

Space

O(m × n)recursion stack in the worst case (all land)

Visualization

Input:

DFS Traversal4×4 grid

output—

Press play to start dfs traversal

CurrentQueuedVisitedSource

34 steps

Solution Code

Number of Islands

Clone Graph