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.In #695 Max Area of Island, you are given a binary matrix where 1 represents land and 0 represents water. The goal is to compute the maximum area of a connected island. Two cells belong to the same island if they are connected horizontally or vertically.
The most common approach is to use Depth-First Search (DFS) or Breadth-First Search (BFS). Iterate through every cell in the grid, and whenever you encounter an unvisited land cell (1), start a traversal to explore all connected land cells. Mark visited cells to avoid reprocessing and count the total cells in that island. Track the maximum area encountered during the traversal.
Another possible method uses the Union Find (Disjoint Set) data structure to group adjacent land cells into connected components and maintain their sizes.
The DFS/BFS traversal visits each cell at most once, giving a time complexity of O(m × n) and space complexity depending on recursion or queue usage.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| DFS / BFS Traversal | O(m × n) | O(m × n) worst case due to recursion stack or queue |
| Union Find | O(m × n α(m × n)) | O(m × n) |
NeetCode
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.
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.
1#include <stdio.h>
2
3#define MAX 50
4
5int dfs(int grid[MAX][MAX], int visited
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.
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.
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.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, grid traversal problems like Max Area of Island are commonly asked in FAANG and other top tech interviews. They test understanding of DFS, BFS, graph traversal, and matrix-based problem solving.
Graphs represented through grid traversal are typically solved using recursion or a queue with DFS or BFS. Alternatively, Union Find can be used to group adjacent land cells and maintain island sizes efficiently.
The optimal approach is to use DFS or BFS traversal. Start exploring whenever you encounter a land cell and count all connected land cells while marking them visited. This ensures each cell is processed once, resulting in O(m × n) time complexity.
Marking cells as visited prevents counting the same land cell multiple times and avoids infinite loops during traversal. It ensures each cell contributes to the island area exactly once.
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.