How do you solve Max Area of Island on LeetCode?

Max Area of Island (LeetCode #695) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n²) time complexity and O(1) space complexity. Key insight: Islands are defined by 1's connected 4-directionally.

What is the brute force solution for Max Area of Island?

The brute force approach for Max Area of Island is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves checking every cell in the grid. Whenever we find a '1', we can perform a depth-first search (DFS) to explore the entire island and count its area. The optimal Optimal Solution approach improves this to O(n²).

What algorithm or data structure is used to solve Max Area of Island?

Max Area of Island uses the following concepts: Array, Depth-First Search, Breadth-First Search, Union-Find, Matrix. The recommended patterns to study are: Depth-First Search, Breadth-First Search, Matrix Traversal.

What are the interview tips for Max Area of Island?

Clarify the definition of an island before starting. Think about edge cases, such as grids with no land. Discuss your thought process and approach before coding.

What are common mistakes when solving Max Area of Island?

Not marking cells as visited, leading to infinite loops. Confusing the connectivity rules (4-directional vs 8-directional).

#695

Max Area of Island

Medium

ArrayDepth-First SearchBreadth-First SearchUnion-FindMatrixDepth-First SearchBreadth-First SearchMatrix Traversal

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n²)
Space	O(1)	O(1)

💡

Intuition

Time O(n²)Space O(1)

The optimal solution uses a similar DFS approach but can be more efficient in terms of implementation and clarity. We can also use breadth-first search (BFS) if preferred.

⚙️

Algorithm

5 steps

1Step 1: Initialize a variable to keep track of the maximum area found.
2Step 2: Loop through each cell in the grid. If a cell contains '1', initiate a DFS or BFS to calculate the area of the island.
3Step 3: In the DFS/BFS, mark the cell as visited and explore its neighbors, counting the number of cells visited.
4Step 4: After the DFS/BFS completes, compare the area found with the maximum area and update if necessary.
5Step 5: Continue until all cells are checked and return the maximum area.

solution.py21 lines

1# Full working Python code
2
3def maxAreaOfIsland(grid):
4    def dfs(i, j):
5        if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == 0:
6            return 0
7        grid[i][j] = 0  # Mark as visited
8        area = 1  # Count this cell
9        area += dfs(i + 1, j)
10        area += dfs(i - 1, j)
11        area += dfs(i, j + 1)
12        area += dfs(i, j - 1)
13        return area
14
15    max_area = 0
16    for i in range(len(grid)):
17        for j in range(len(grid[0])):
18            if grid[i][j] == 1:
19                max_area = max(max_area, dfs(i, j))
20    return max_area
21

ℹ

Complexity note: The time complexity remains O(n²) due to visiting each cell, but the implementation is clearer. The space complexity is O(1) as we only use the stack for DFS.

1Islands are defined by 1's connected 4-directionally.
2DFS or BFS can be used to explore and count the area of islands.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.