Graphs · 073Medium
Max Area of Island
Given an m x n binary grid where 1 is land and 0 is water, return the area of the largest island (land connected 4-directionally). Return 0 if there is no island.
Constraints
- 1 <= m, n <= 50
- grid[i][j] is 0 or 1.
Examples
maxAreaOfIsland([[0,1],[1,0]]) -> 1 // diagonals do not connect maxAreaOfIsland([[1,1],[1,0]]) -> 3 maxAreaOfIsland([[0,0],[0,0]]) -> 0 maxAreaOfIsland([[1]]) -> 1 // smallest grid, one land cell maxAreaOfIsland([[0]]) -> 0 // smallest grid, no land maxAreaOfIsland([[1,1],[1,1]]) -> 4 // the whole grid is one island
Edge cases
- A grid of all water returns 0.
- Diagonal neighbors are NOT connected.
Show the target complexity (spoiler)
- Naive
- Re-exploring islands without marking visited cells double-counts and may not
- Target
- O(m * n) time — flood-fill from each unvisited land cell, returning the cell count, and keep the maximum.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/08-graphs/073-max-area-of-island.js ./practice c 073