DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Number of Islands

mediumGraphs Must-do

Problem statement

You get a 2D grid of characters where "1" is land and "0" is water. An island is a group of land cells joined up, down, left or right (not diagonally). Everything outside the grid counts as water.

Return the number of islands.

Examples

Example 1

Input: grid = [["1","0","1"], ["1","0","0"], ["0","1","1"]]

Output: 3

Explanation: The left column pair, the top-right cell, and the bottom-right pair are three separate islands.

Example 2

Input: grid = [["1","1","0","0"], ["0","1","1","0"], ["0","0","0","1"]]

Output: 2

Explanation: The staircase of four cells is one island. The bottom-right cell touches it only diagonally, so it is a second island.

Hints

Approach

Same scan, but explore each island with an iterative breadth-first search and "sink" land by overwriting it with "0" as soon as it is queued.

  1. Walk every cell. On a "1", add one to the count, set it to "0" and push it onto a queue.
  2. Pop a cell and look at its four neighbours. Each neighbour that is inside the grid and still "1" is set to "0" and pushed.
  3. When the queue empties, the whole island is gone, so the outer scan will never count it again.

Sinking on enqueue (not on dequeue) matters: it stops the same cell being pushed twice by two different neighbours. There is no recursion, so large grids are safe, and no visited set. The queue holds only the current frontier of one island, which is usually much smaller than the grid, though O(m * n) is the safe worst-case bound. If the caller's grid must not change, copy it first.

ComplexityTime O(m * n)Space O(m * n)
Python
from collections import deque
class Solution:
def numIslands(self, grid: list[list[str]]) -> int:
rows, cols = len(grid), len(grid[0])
count = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] != "1":
continue
count += 1
grid[r][c] = "0" # sink on enqueue
queue = deque([(r, c)])
while queue:
cr, cc = queue.popleft()
for nr, nc in ((cr + 1, cc), (cr - 1, cc), (cr, cc + 1), (cr, cc - 1)):
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == "1":
grid[nr][nc] = "0"
queue.append((nr, nc))
return count

Follow-up questions

  • Return the size of the largest island instead of the count.
  • Land cells are added one by one; report the island count after each addition without rescanning the grid.

Frequently asked questions

The BFS queue only holds the current frontier of one island, which is usually far smaller than the grid. The worst case is still proportional to the island's size, so say O(m * n) if the interviewer wants a strict bound. The saving that always holds is dropping the visited set.

The grid is just a graph where each cell has up to four neighbours. Counting connected groups is the same question as counting network partitions after links fail, or grouping hosts into clusters that can reach each other. Grid problems test whether you can see the graph without being handed an edge list.

Yes: union each land cell with its land neighbours to the right and below, then count distinct roots. It is the better choice when land appears one cell at a time and you must report the island count after each addition.