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 either 0 or 1.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.
In this approach, we will use Depth First Search (DFS) to explore the grid. The idea is to iterate over each cell in the grid and apply DFS when we encounter an unvisited cell that is a part of an island (i.e., grid value is 1). We will mark each visited cell to avoid revisiting. By keeping a count of the size of each island found, we can track the maximum size encountered.
This C solution defines a DFS function that recursively counts connected land cells. A visited matrix is used to ensure cells are only counted once. The main function iterates over all cells in the grid and updates the maximum area found.
Time Complexity: O(m * n), where m is the number of rows and n is the number of columns. Each cell is visited once.
Space Complexity: O(m * n), used for the visited matrix and recursion stack.
A Breadth First Search (BFS) approach can also be used to solve this problem by iteratively exploring each cell's neighbors using a queue and counting the size of islands found. By enqueueing all land cell neighbors for exploration and tracking maximum sizes found, we can also determine the maximum island area.
This BFS C solution uses a queue to iteratively visit all land cells in a discovered island, marking them visited as they are dequeued. Queue-based exploration ensures that contiguous cells are considered in groups.
Time Complexity: O(m * n), since all cells are enqueued and dequeued once.
Space Complexity: O(m * n), required for the queue and the visited matrix.
| Approach | Complexity |
|---|---|
| Depth First Search (DFS) Approach | Time Complexity: O(m * n), where m is the number of rows and n is the number of columns. Each cell is visited once. |
| Breadth First Search (BFS) Approach | Time Complexity: O(m * n), since all cells are enqueued and dequeued once. |
| Default Approach | — |
| 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 |
Max Area of Island - Leetcode 695 - Python • NeetCode • 89,090 views views
Watch 9 more video solutions →Practice Max Area of Island with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor