#200 Number of Islands
frequently reported atByteDance / TikTokWalmartSamsungUberAmazonBloomberg
the problem
In plain words
A grid has '1' (land) and '0' (water). Land cells connect up, down, left and right (not diagonally). Count the islands.
in grid = [[1,1,1,1,0],[1,1,0,1,0],[1,1,0,0,0],[0,0,0,0,0]]
out 1
in grid = [[1,1,0,0,0],[1,1,0,0,0],[0,0,1,0,0],[0,0,0,1,1]]
out 3
- 1 ≤ m, n ≤ 300
- grid[i][j] is '0' or '1'
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternGrid flood fillGraph DFS / BFS traversalUnion-Find (DSU)
Islands are connected components. Scan every cell; untouched land starts a new island, and a flood fill sinks the whole island so it can never be counted again.
solutions
From brute force to optimal
For each '1', count it and recursively turn its whole island into '0'.
- Loop over all cells.
- On a '1': islands++, then DFS that sets cells to '0' and recurses in 4 directions.
- The DFS returns immediately on out-of-bounds or water.
Each cell is scanned once and sunk at most once; each sink tries 4 neighbours.
Worst case (all land) the recursion can go m·n deep.
class Solution { public int numIslands(char[][] grid) { int islands = 0; for (int r = 0; r < grid.length; r++) for (int c = 0; c < grid[0].length; c++) if (grid[r][c] == '1') { islands++; sink(grid, r, c); } return islands; } /** Turns the whole island containing (r, c) into water so it is never counted again. */ private void sink(char[][] grid, int r, int c) { if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length || grid[r][c] != '1') return; grid[r][c] = '0'; sink(grid, r + 1, c); sink(grid, r - 1, c); sink(grid, r, c + 1); sink(grid, r, c - 1); }}Dry run
Same idea, but sink each island with a queue — no recursion depth limit.
- On a '1': islands++, set it to '0', enqueue it.
- Poll cells; set each land neighbour to '0' when enqueuing it.
Each cell enters the queue at most once.
The queue holds at most the cells of one island — bounded by m·n (in practice much less: about one "ring").
class Solution { public int numIslands(char[][] grid) { int rows = grid.length, cols = grid[0].length, islands = 0; int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; for (int r = 0; r < rows; r++) for (int c = 0; c < cols; c++) { if (grid[r][c] != '1') continue; islands++; grid[r][c] = '0'; // mark on enqueue so no cell is queued twice Deque<int[]> queue = new ArrayDeque<>(); queue.offer(new int[] {r, c}); while (!queue.isEmpty()) { int[] cell = queue.poll(); for (int[] d : dirs) { int nr = cell[0] + d[0], nc = cell[1] + d[1]; if (nr < 0 || nc < 0 || nr >= rows || nc >= cols || grid[nr][nc] != '1') continue; grid[nr][nc] = '0'; queue.offer(new int[] {nr, nc}); } } } return islands; }}Every land cell starts as its own group; union neighbouring land cells; count the groups left.
- count = number of land cells.
- For each land cell, union with the land cell to its right and below.
- Every successful union does count--.
≈ 2·m·n unions; path halving keeps each find O(log) amortized — near-constant in practice (add union by rank for α).
The parent array has one slot per cell.
class Solution { private int[] parent; private int count; // number of separate land groups public int numIslands(char[][] grid) { int rows = grid.length, cols = grid[0].length; parent = new int[rows * cols]; for (int r = 0; r < rows; r++) for (int c = 0; c < cols; c++) if (grid[r][c] == '1') { parent[r * cols + c] = r * cols + c; // each land cell starts alone count++; } for (int r = 0; r < rows; r++) for (int c = 0; c < cols; c++) { if (grid[r][c] != '1') continue; // Only look right and down: every adjacent pair is still seen once. if (r + 1 < rows && grid[r + 1][c] == '1') union(r * cols + c, (r + 1) * cols + c); if (c + 1 < cols && grid[r][c + 1] == '1') union(r * cols + c, r * cols + c + 1); } return count; } private int find(int x) { while (parent[x] != x) { parent[x] = parent[parent[x]]; // path halving keeps trees flat x = parent[x]; } return x; } private void union(int a, int b) { int ra = find(a), rb = find(b); if (ra != rb) { parent[ra] = rb; count--; // two groups merged into one } }}in the room
How to say it in the interview
talk track
- Clarify: diagonal cells don't connect; may I modify the grid? (If not, use a
boolean[][] visited.) - Say: "Islands are connected components in a grid graph. I scan, and each unvisited land cell starts a flood fill."
- State O(m·n) time; mention the recursion depth risk and that BFS avoids it.
traps
- Counting inside the DFS instead of once per new start.
- Checking
grid[r][c]before the bounds check.
what they ask next
Follow-ups
Max Area of Island (LC 695)?
Same scan; make the DFS return the size of what it sank (1 + the four recursive results) and keep the max.
Number of Islands II (LC 305): land is added one cell at a time?
Union-Find shines: add the cell, union with land neighbours, report the count after each addition — no re-scan.
before you submit
Edge cases to test
- All water → 0.
- A single land cell → 1.
- Diagonal neighbours do not connect: a checkerboard of 1s has one island per 1.
- One big island shaped like a snake: recursion depth equals its size — BFS avoids deep recursion.
practise next
Similar problems
- #695Max Area of IslandMediumin Graphs
- #733Flood FillEasyin Graphs
- #130Surrounded RegionsMediumin Graphs
- #547Number of ProvincesMediumin Union-Find & MST