Max Area of Island - Video Solutions
Max Area of Island - Leetcode 695 - Python
Max Area of Island - Video Solution
Watch 10 video solutions for Max Area of Island, a medium level problem involving Array, Depth-First Search, Breadth-First Search. This walkthrough by NeetCode has 93,044 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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.
Example 1:
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 answer is not 11, because the island must be connected 4-directionally.
Example 2:
Input: grid = [[0,0,0,0,0,0,0,0]] Output: 0
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 50grid[i][j]is either0or1.
Approach Overview
Problem Overview: You get an m x n binary grid where 1 represents land and 0 represents water. An island is a group of connected land cells (4-directionally). The task is to compute the maximum number of cells in any island.
Approach 1: Depth First Search (DFS) Flood Fill (O(m*n) time, O(m*n) space)
Scan the grid and start a DFS whenever you encounter an unvisited land cell. The DFS recursively explores all 4 directions (up, down, left, right) and counts how many cells belong to that island. Mark each visited cell as 0 or store it in a visited set so it is not counted again. Each cell is processed once, so the traversal cost is linear in the grid size. DFS is simple to implement and fits naturally with recursion when solving Depth-First Search problems on a matrix.
Approach 2: Breadth First Search (BFS) Traversal (O(m*n) time, O(m*n) space)
BFS solves the same flood-fill problem using a queue instead of recursion. When a land cell is found, push it into a queue and repeatedly process neighbors while counting the island size. Each step dequeues a cell, checks the four directions, and enqueues any unvisited land cells. BFS avoids recursion depth issues and can be easier to reason about in iterative environments. This approach is common in grid traversal questions involving Breadth-First Search.
Approach 3: Union Find (Disjoint Set) (O(m*n α(n)) time, O(m*n) space)
Union Find treats every land cell as a node in a disjoint-set structure. As you iterate through the grid, union adjacent land cells into the same set. Maintain a size array that tracks how many cells belong to each component. The maximum component size becomes the largest island. Path compression and union by rank keep operations near constant time. This approach is useful when you already model the grid as connected components using Union Find, though it is more complex than DFS or BFS.
Recommended for interviews: DFS or BFS flood fill is the expected solution. Both run in O(m*n) time because every cell is visited at most once. DFS is slightly shorter to write in most languages, while BFS avoids recursion limits. Interviewers typically want to see correct grid traversal, boundary checks, and visited marking. Union Find demonstrates deeper graph modeling but is rarely necessary for this problem.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Depth First Search (DFS) | O(m*n) | O(m*n) | Most common interview solution; simple recursive flood fill |
| Breadth First Search (BFS) | O(m*n) | O(m*n) | When avoiding recursion depth or preferring iterative traversal |
| Union Find (Disjoint Set) | O(m*n α(n)) | O(m*n) | When modeling connected components or solving dynamic connectivity problems |