Max Area of Island
The key idea
Every
1 belongs to exactly one island. Flood-fill from each unvisited land cell, counting how many 1s the flood reaches, and sink each visited cell to 0 so it is never counted twice. The largest flood count is the answer.Problem
You are given an m x n binary matrix grid. An island is a group of 1s (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 value 1 in the island.
Return the maximum area of an island in grid. If there is no island, return 0.
Constraints
m == grid.lengthn == grid[i].length1 <= m, n <= 50grid[i][j]is either0or1
Examples
Input: grid = [[0,0,1,0,0],[0,1,1,0,0],[0,0,0,1,1]]
Output: 3
Input: grid = [[0,0,0,0],[0,0,0,0]]
Output: 0
Complexity
Time: O(m*n) Space: O(m*n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More BFS / DFS problems
- 01 MatrixMEDIUM
- Average of Levels in Binary TreeEASY
- Binary Tree Level Order TraversalMEDIUM
- Binary Tree Level Order Traversal IIMEDIUM
- Binary Tree Right Side ViewMEDIUM
- Binary Tree Zigzag Level Order TraversalMEDIUM
- Find Bottom Left Tree ValueMEDIUM
- Find Largest Value in Each Tree RowMEDIUM
- Flood FillEASY
- Keys and RoomsMEDIUM
- Maximum Level Sum of a Binary TreeMEDIUM
- Minimum Depth of Binary TreeEASY