Number of Islands is the single most common graph question in interviews, and the reason is that it
does not look like a graph question. There is no adjacency list and no Node class —
just a grid. Recognising that a grid is a graph, where each cell is a vertex and its four
neighbours are its edges, is most of what is being tested.
The problem
Given a 2-D grid of '1' (land) and '0' (water), count the islands. An
island is land connected horizontally or vertically — not diagonally — and the grid
edges count as water.
11110 11000
11010 11000 -> 3
11000 -> 1 00100
00000 00011Confirm the diagonal rule before writing anything. It is the one genuine ambiguity in the statement, it changes the answer on the second example, and asking costs you five seconds.
The idea: count starts, then erase
Scan every cell. When you find land that has not been visited, you have found a new island — increment the count, then flood the entire connected region so no other cell of it can start a second count.
That is the whole algorithm, and the flood can be depth-first or breadth-first; it makes no difference to the answer because you are not measuring distances, only reachability. The count is driven by the outer scan; the flood exists purely to stop double-counting.
The line that matters
Mark the cell visited before you recurse, not after. Two adjacent land cells are each other's neighbours, so without marking first, cell A recurses into B, which recurses straight back into A, forever. This is the bug that turns the problem from ten minutes into thirty.
The cheapest mark is to overwrite the cell with '0' — "sinking" the island. It costs
no extra memory and the bounds check that guards the recursion doubles as the visited check, since a
sunk cell is no longer '1'.
It also destroys the input. That is a trade worth naming out loud rather than
doing silently: it is fine when the grid is scratch data, and unacceptable if the caller still needs
it. The alternative is a parallel boolean[][] visited, costing O(rows·cols)
extra space. Say which you are doing and why.
Java
class Solution {
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) return 0;
int count = 0;
for (int r = 0; r < grid.length; r++) {
for (int c = 0; c < grid[0].length; c++) {
if (grid[r][c] == '1') {
count++; // a cell no flood has reached: a new island
sink(grid, r, c); // erase it so it cannot be counted twice
}
}
}
return count;
}
private void sink(char[][] grid, int r, int c) {
if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] != '1') {
return; // off the grid, water, or already sunk
}
grid[r][c] = '0'; // BEFORE recursing, or neighbours bounce back into each other
sink(grid, r + 1, c);
sink(grid, r - 1, c);
sink(grid, r, c + 1);
sink(grid, r, c - 1);
}
}Putting every rejection into one guard at the top of sink — rather than checking
before each of the four calls — is what keeps this short. The four recursive calls need no
conditions at all.
Python
class Solution:
def numIslands(self, grid: list[list[str]]) -> int:
if not grid or not grid[0]:
return 0
rows, cols = len(grid), len(grid[0])
def sink(r: int, c: int) -> None:
if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != "1":
return
grid[r][c] = "0" # mark before recursing
sink(r + 1, c)
sink(r - 1, c)
sink(r, c + 1)
sink(r, c - 1)
count = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == "1":
count += 1
sink(r, c)
return countWhy you might want BFS instead
DFS recursion depth is the size of the largest island. A grid that is entirely land recurses
rows × cols deep — on a 300×300 board that is 90,000 frames, which overflows the Java
stack and blows straight past Python's default recursion limit of 1000. BFS with an explicit queue
has the same O(rows·cols) memory bound but keeps it on the heap:
private static final int[][] DIRECTIONS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
private void sinkBfs(char[][] grid, int startRow, int startCol) {
Deque<int[]> queue = new ArrayDeque<>();
grid[startRow][startCol] = '0'; // mark on ENQUEUE, not on dequeue
queue.add(new int[]{startRow, startCol});
while (!queue.isEmpty()) {
int[] cell = queue.poll();
for (int[] d : DIRECTIONS) {
int r = cell[0] + d[0], c = cell[1] + d[1];
if (r >= 0 && r < grid.length && c >= 0 && c < grid[0].length
&& grid[r][c] == '1') {
grid[r][c] = '0';
queue.add(new int[]{r, c});
}
}
}
}The same "mark first" rule applies, and here it is even easier to get wrong: mark on enqueue, not on dequeue. Marking at dequeue lets a cell be added to the queue by several neighbours before it is ever processed, which is not incorrect but can blow the queue up quadratically.
The direction array is worth the two lines. Four hand-written recursive calls are fine; four hand-written bounds checks are where typos live.
Complexity
O(rows · cols) time — every cell is examined by the outer scan once and sunk at most
once. Space is O(rows · cols) in the worst case for the recursion stack or the queue,
when the whole grid is one island. Sinking in place adds nothing; a visited array would
add another O(rows · cols).
The variants you should expect
- Max Area of Island (695) — same flood, but return a size and take the maximum. Usually asked as a direct follow-up.
- Surrounded Regions (130) — flood inwards from the borders to mark what is safe, then flip the rest. The trick is realising you should start from the outside.
- Rotting Oranges (994) — BFS is now mandatory, because the answer is a number of steps and DFS does not measure distance.
- Number of Islands II (305) — land is added one cell at a time and the count is reported after each addition. Re-flooding every time is too slow; this is the union-find problem.
What the interviewer is checking
- That you see a grid as a graph without being told.
- That you mark cells visited before recursing.
- That you asked about diagonals.
- That you say out loud whether you are mutating the input, and offer the alternative.
- That you know the recursion depth is the island size, and when that forces BFS.
- An empty grid, a single cell, an all-water grid, and an all-land grid.