Max Area of Island
You are given a grid of 0s and 1s. A 1 is land and a 0 is water. An island is a group of 1s joined up, down, left or right (never diagonally). Return the area of the largest island , where area means how many 1s it contains. Return 0 if there is no land at all. Walk the grid cell by cell. When you land on a 1, run a flood fill that counts every connected 1 and turns each one into a 0 as it goes, so the same island is never counted twice.
Constraints
- 1 ≤ grid.length, grid0.length ≤ 50
- Every cell is 0 or 1
- Cells joined only at a corner are not part of the same island
- The input grid is changed in place by this solution
Example
grid = [[1, 0, 1], [1, 0, 0]]2Explanation There are two islands: the pair at (0,0) and (1,0) with area 2, and the single cell at (0,2) with area 1. The largest is 2.
In plain terms
- Grid as a graph
- Each cell is a node, and each cell is joined to the neighbour above, below, left and right of it. That makes a grid just another graph.
- Flood fill
- Starting at one cell and spreading out to every connected cell of the same kind, like a paint bucket in a drawing program.
- Sinking a cell
- Writing a 0 over a 1 once you have counted it. It is a cheap way to mark a cell as visited without a second grid.
- Recursion
- A function calling itself on a smaller piece of the problem. Here the function calls itself on each of the four neighbours.
One cell per grid square, read row by row, value = 1 for land and 0 for water
The grid starts with three land squares and the best area so far is zero.
What happens in this step
grid = [[1, 0, 1],
[1, 0, 0]]
best = 0
Land sits at (0,0), (0,2) and (1,0).
Nothing has been counted yet.Steps to visualize
- The 2 by 3 grid is laid out flat: the first three cells are row 0 and the last three are row 1.
- Labels are row,column and values are the current contents of that square.
- Scan the cells in order and stop at the first 1 you meet.
- Flood fill from there: count that square, sink it to 0, then do the same to its four neighbours.
- Remember the biggest count you have seen and carry on scanning.
Walk through the code
Same walkthrough, now with the code. Press Next to move one step and watch which lines run.
The grid starts with three land squares and the best area so far is zero.
What happens in this step
grid = [[1, 0, 1],
[1, 0, 0]]
best = 0
Land sits at (0,0), (0,2) and (1,0).
Nothing has been counted yet.Solution
function maxAreaOfIsland(grid) {
const rows = grid.length;
const cols = grid[0].length;
let best = 0;
function area(r, c) {
if (r < 0 || c < 0 || r >= rows || c >= cols) return 0;
if (grid[r][c] !== 1) return 0;
grid[r][c] = 0;
return 1 + area(r + 1, c) + area(r - 1, c) + area(r, c + 1) + area(r, c - 1);
}
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (grid[r][c] === 1) {
best = Math.max(best, area(r, c));
}
}
}
return best;
}- Time
- O(rows * cols)
- Space
- O(rows * cols) for the recursion in the worst case
Test cases
| Input | Expected | Covers |
|---|---|---|
grid = [[1, 0, 1], [1, 0, 0]] | 2 | example from the docstring |
grid = [[0, 0], [0, 0]] | 0 | a grid with no land at all |
grid = [[1, 1], [1, 1]] | 4 | every square is part of one island |
grid = [[1]] | 1 | smallest possible grid |
grid = [[0, 1, 0], [1, 1, 1], [0, 1, 0]] | 5 | an island that spreads in all four directions |
grid = [[1, 1, 0, 0], [1, 0, 0, 1], [0, 0, 1, 1]] | 3 | two separate islands of the same size, with a diagonal touch that does not join them |