The largest island
A grid holds 1 for land and 0 for water. An island is a group of land cells
connected through shared sides (up, down, left, right). Return the number of cells in the largest island, or
0 if there is no land.
Examples
| Input | Output | Why |
|---|---|---|
grid = [[0,0,1,0,0],[1,1,1,0,0],[0,1,0,0,1],[0,0,0,1,1]] | 5 | The island on the left has five cells; the one on the right has three. |
grid = [[1,0,1],[0,1,0],[1,0,1]] | 1 | Diagonal cells are not connected: five islands of one cell. |
grid = [[1,1,1],[1,0,1],[1,1,1]] | 8 | A ring of eight cells around a lake. |
Constraints
- 1 ≤ rows, cols ≤ 50
- Every cell is 0 or 1
Hints
Hint 1
This is the components template with f = "count the cells" and g = "maximum".
Hint 2
Scan the grid; at each land cell not yet visited, flood the whole island, counting cells as you mark them.
Hint 3
Keep the largest count seen.
Where people lose marks
- Counting diagonal neighbours as connected.
- Counting a cell each time it is reached rather than once, when it is first marked.
- Returning the number of islands instead of the size of the largest one.
Dry run on [[0,0,1,0,0],[1,1,1,0,0],[0,1,0,0,1],[0,0,0,1,1]]
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 2largest5
New land at (0, 2): flood island A, 5 cells. Largest so far: 5.
-
Step 2 / 2largest5
New land at (2, 4): flood island B, 3 cells. Largest so far: 5. The scan is complete: the answer is 5.
How to think about it
Each island is a connected component of land cells. Scan every cell; an unvisited land cell starts a new island. Flood it with an explicit stack, marking each cell when it is pushed and adding one to the island's size. When the stack empties, compare the size with the best so far.
Every cell is pushed at most once, so the whole scan is linear in the size of the grid.
Complexity. Time O(rows · cols) · Space O(rows · cols)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def max_island_area(grid):
rows, cols = len(grid), len(grid[0])
seen = [[False] * cols for _ in range(rows)]
best = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] != 1 or seen[r][c]:
continue
seen[r][c] = True
stack, size = [(r, c)], 1 # a new island: flood it and count
while stack:
i, j = stack.pop()
for a, b in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
if 0 <= a < rows and 0 <= b < cols and grid[a][b] == 1 and not seen[a][b]:
seen[a][b] = True
size += 1
stack.append((a, b))
best = max(best, size)
return best#include <algorithm>
#include <utility>
#include <vector>
int solve(const std::vector<std::vector<int>>& grid) {
const int rows = grid.size(), cols = grid[0].size();
std::vector<std::vector<bool>> seen(rows, std::vector<bool>(cols, false));
const int dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1};
int best = 0;
for (int r = 0; r < rows; ++r)
for (int c = 0; c < cols; ++c) {
if (grid[r][c] != 1 || seen[r][c]) continue;
seen[r][c] = true;
std::vector<std::pair<int, int>> stack{{r, c}};
int size = 1; // flood the island and count it
while (!stack.empty()) {
auto [i, j] = stack.back();
stack.pop_back();
for (int k = 0; k < 4; ++k) {
int a = i + dr[k], b = j + dc[k];
if (a >= 0 && b >= 0 && a < rows && b < cols && grid[a][b] == 1 && !seen[a][b]) {
seen[a][b] = true; ++size; stack.push_back({a, b});
}
}
}
best = std::max(best, size);
}
return best;
}import java.util.*;
class Solution {
public int maxIslandArea(int[][] grid) {
int rows = grid.length, cols = grid[0].length, best = 0;
boolean[][] seen = new boolean[rows][cols];
int[] dr = {1, -1, 0, 0}, dc = {0, 0, 1, -1};
for (int r = 0; r < rows; r++)
for (int c = 0; c < cols; c++) {
if (grid[r][c] != 1 || seen[r][c]) continue;
seen[r][c] = true;
ArrayDeque<int[]> stack = new ArrayDeque<>();
stack.push(new int[]{r, c});
int size = 1; // flood the island and count it
while (!stack.isEmpty()) {
int[] cell = stack.pop();
for (int k = 0; k < 4; k++) {
int a = cell[0] + dr[k], b = cell[1] + dc[k];
if (a >= 0 && b >= 0 && a < rows && b < cols && grid[a][b] == 1 && !seen[a][b]) {
seen[a][b] = true; size++; stack.push(new int[]{a, b});
}
}
}
best = Math.max(best, size);
}
return best;
}
}function maxIslandArea(grid) {
const rows = grid.length, cols = grid[0].length;
const seen = Array.from({ length: rows }, () => new Array(cols).fill(false));
let best = 0;
for (let r = 0; r < rows; r++) for (let c = 0; c < cols; c++) {
if (grid[r][c] !== 1 || seen[r][c]) continue;
seen[r][c] = true;
const stack = [[r, c]];
let size = 1; // flood the island and count it
while (stack.length) {
const [i, j] = stack.pop();
for (const [a, b] of [[i + 1, j], [i - 1, j], [i, j + 1], [i, j - 1]]) {
if (a >= 0 && b >= 0 && a < rows && b < cols && grid[a][b] === 1 && !seen[a][b]) {
seen[a][b] = true; size++; stack.push([a, b]);
}
}
}
best = Math.max(best, size);
}
return best;
}fn solve<const C: usize>(grid: &[[i64; C]]) -> i64 {
let rows = grid.len();
let mut seen = vec![[false; C]; rows];
let mut best = 0;
for r in 0..rows {
for c in 0..C {
if grid[r][c] != 1 || seen[r][c] {
continue;
}
seen[r][c] = true;
let mut stack = vec![(r, c)];
let mut size = 1; // flood the island and count it
while let Some((i, j)) = stack.pop() {
let around = [(i + 1, j), (i.wrapping_sub(1), j), (i, j + 1), (i, j.wrapping_sub(1))];
for (a, b) in around {
if a < rows && b < C && grid[a][b] == 1 && !seen[a][b] {
seen[a][b] = true;
size += 1;
stack.push((a, b));
}
}
}
best = best.max(size);
}
}
best
}import qualified Data.Set as S
solve :: [[Int]] -> Int
solve grid = go (S.toList land) S.empty 0
where
land = S.fromList [(r, c) | (r, row) <- zip [0 ..] grid, (c, 1) <- zip [0 ..] row]
go [] _ best = best
go (p : ps) seen best
| S.member p seen = go ps seen best
| otherwise = let island = flood [p] (S.singleton p)
in go ps (S.union seen island) (max best (S.size island))
-- every land cell reachable from the stack, through shared sides
flood [] acc = acc
flood ((r, c) : st) acc =
let next = [q | q <- [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)], S.member q land, not (S.member q acc)]
in flood (next ++ st) (foldr S.insert acc next)Variants to try
- You may turn one water cell into land: what is the largest island you can make? (Label islands with ids and sizes, then try each water cell.)
- Return the sizes of all islands in decreasing order.
- The grid is too large for memory and arrives row by row: keep union-find labels for the previous row only.
Next problems
Count the islands in a grid
Every unvisited land cell starts a new island; flood it so it is never counted again. The first graph problem most interviews ask.
Open the problem → Medium15 minCount the friend groups
People know each other directly or through friends. Count the separate groups, given an n × n matrix of who knows whom.
Open the problem → Medium15 minThe cheapest node in each group
Each node has a value. Find the smallest value in every connected group and return their sum: the components template with f = min and g = sum.
Open the problem →Write a solution and run it against the real test table.
Keep going
Count the islands in a grid
Every unvisited land cell starts a new island; flood it so it is never counted again. The first graph problem most interviews ask.
Open the problem → Medium15 minCount the friend groups
People know each other directly or through friends. Count the separate groups, given an n × n matrix of who knows whom.
Open the problem → Medium15 minThe cheapest node in each group
Each node has a value. Find the smallest value in every connected group and return their sum: the components template with f = min and g = sum.
Open the problem → GraphsThe pattern behind it
Grids, networks and dependencies are all graphs. Breadth-first search finds shortest paths, depth-first search and union-find find what is connected, Dijkstra handles weighted edges, and a queue of nodes with no remaining prerequisites gives an order.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.