Biggest Island
Medium · Graphs · Array · Depth-First Search · Breadth-First Search · Matrix
Problem
You are given an m x n binary matrix grid, where 1 is land and 0 is water. An island is a group of land cells connected horizontally or vertically (not diagonally). Everything outside the grid is water.
The area of an island is the number of land cells in it. Return the area of the biggest island, or 0 if there is no land.
Examples
Input: grid = [[1,1,0,0],[1,0,0,1],[0,0,1,1],[0,0,0,1]] Output: 4
The top-left island has 3 cells; the one on the right has 4.
Input: grid = [[0,0],[0,0]] Output: 0
There is no land at all.
Input: grid = [[1,0,1],[0,1,0],[1,0,1]] Output: 1
The cells touch only at corners, so each is its own island of area 1.
Constraints
- m == len(grid), n == len(grid[i])
- 1 <= m, n <= 50
- grid[i][j] is 0 or 1
Approaches
- Explore every cell’s island from scratch — time O((m · n)²), space O(m · n)
Follow-up
What if you may turn one water cell into land? Label each island with its area first, then for each water cell add up the distinct islands around it. That is a separate problem built on the same flood fill.
Related problems
Start free on Cariara · Coding problems · System design studio
