695. Max Area of Island - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

Description:
You are given an $( m \times n )$ binary matrix grid where:

1 represents land.
0 represents water.

An island is defined as a group of 1's connected horizontally or vertically. The area of an island is the total number of cells with value 1 in that island. The task is to find the maximum area of any island in the grid. If no island exists, return 0.

Constraints:

$( 1 \leq m, n \leq 50 )$ (typical constraints, though they may vary)
Each element in grid is either 0 or 1.

Example 1:

Input:

grid = [
  [0,0,1,0,0],
  [0,1,1,1,0],
  [0,0,1,0,0],
  [1,0,0,0,1]
]

Output: 5
Explanation:
The largest island is in the center with area 5 (the connected 1's form a plus shape). Note that the islands in the bottom corners have area 1.

Example 2:

Input:

grid = [
  [0,0,0],
  [0,0,0],
  [0,0,0]
]

Output: 0
Explanation:
There is no island because all cells are 0.

Hints

Hint 1: Think about how you can traverse all connected parts of an island. A common technique is to use Depth-First Search (DFS) or Breadth-First Search (BFS) to “mark” visited cells so that you don’t count the same island multiple times.
Hint 2: For every cell with a value of 1 that hasn’t been visited, start a traversal (DFS/BFS) to calculate the island’s area. Update your maximum area when you finish traversing an island.

Approaches

Approach 1: Depth-First Search (DFS)

Idea:
For each cell in the grid that is 1 and unvisited, perform a DFS to explore the entire island. During the DFS, mark cells as visited (or change their value) to avoid revisiting them.
How It Works:
1. Loop through each cell in the grid.
2. If the cell is 1, call DFS on that cell.
3. In DFS, count the current cell and recursively explore its four neighbors (up, down, left, right) if they are also 1.
4. Update the maximum area using the count from the DFS.
Complexity:
- Time: $(O(m \times n))$ since each cell is visited at most once.
- Space: $(O(m \times n))$ in the worst-case recursion stack (if the grid is filled with 1's).

Approach 2: Breadth-First Search (BFS)

Idea:
Similar to DFS, but use a queue to explore the island level by level.
How It Works:
1. For each unvisited cell with value 1, use BFS to traverse the entire island.
2. During BFS, count the number of cells and mark them as visited.
3. Update the maximum area with the count obtained.
Complexity:
- Time: $(O(m \times n))$ as each cell is processed at most once.
- Space: $(O(\min(m, n)))$ for the queue in the worst-case scenario.

Both approaches are efficient given the grid size constraints.

Python Code

Below is the Python implementation using DFS:

Python3

. . . .

Note: The row[:] is used to pass a copy of the grid since the DFS modifies it.

Java Code

Below is the Java implementation using DFS.

Java

. . . .

Complexity Analysis

Time Complexity:
- In both DFS and BFS approaches, each cell is visited at most once, leading to a time complexity of $(O(m \times n))$ .
Space Complexity:
- DFS: $(O(m \times n))$ in the worst-case (if the island covers the entire grid, the recursion stack could be that deep).
- BFS: $(O(\min(m, n)))$ in the worst-case for the queue.

Step-by-Step Walkthrough & Visual Example

Consider the following grid:

grid = [
  [0, 0, 1, 0],
  [1, 1, 1, 0],
  [0, 1, 0, 0],
  [1, 0, 0, 1]
]

Iteration Start:
Begin scanning the grid from the top-left cell.
First Island Found:
- At position (0,2) you find a 1.
- Start DFS from (0,2):
  - Visit (0,2) → count 1.
  - Check neighbors: (1,2) is 1 → visit it (count becomes 2).
  - From (1,2): visit (1,1) and (1,0) if connected, and (2,2) is water so skip.
  - Continue recursively until all connected 1's are visited.
- Assume the DFS finds the connected island has an area of 5.
Continue Scanning:
- After marking the entire island as visited (set to 0), continue scanning.
- Other isolated 1's (e.g., at (3,0) and (3,3)) are processed similarly, but their areas are smaller (each 1).
Final Result:
The maximum area found during all DFS traversals is 5.

Common Mistakes, Edge Cases & Alternative Variations

Common Mistakes:

Revisiting Cells:
Failing to mark cells as visited, which can lead to infinite loops or overcounting.
Incorrect Boundary Checks:
Not properly checking the boundaries of the grid can result in out-of-bound errors.
Modifying Input:
Sometimes, modifying the input grid in-place is acceptable, but if not, a copy of the grid should be used.

Edge Cases:

Empty or All Water Grid:
If the grid contains no land (1), the output should be 0.
One Large Island:
When the entire grid is one island, ensure your recursion or queue can handle the worst-case depth.

Alternative Variations:

Using BFS:
Instead of DFS, a BFS approach can be used with a queue to explore islands.
Union-Find:
A disjoint set union (DSU) approach could also be applied, though it is less common for grid traversal problems.