Coding interview problems › Graphs & Grids

🗺️ Graphs & Grids Medium

Number of Islands

Number of Islands explained: scan the grid, flood-fill each new piece of land with BFS and count. Tested Python code, common mistakes and a live grid visual.

Also searched as: number of islands leetcode explained · count islands in a grid BFS DFS · connected components in a 2D grid

🏝️

Try it live Free

Number of Islands & Grid BFS

Paint your own map in the Grid BFS lab and run the scan: every time it reaches unseen land it floods that island and adds one to the count.

Also useful: Graph Search: BFS vs DFS, Union-Find (DSU)

Open the playground →

The problem

You are given a 2D grid of '1' (land) and '0' (water). An island is a group of land cells connected up, down, left or right. Count the islands.

Inputgrid = ["11000", "11000", "00100", "00011"]
Output3

Diagonal cells do not connect.

The key insight

Treat the grid as a graph where each land cell links to its land neighbours; an island is a connected component. Scan every cell. When you hit land you have not seen, that is a new island: add one, then flood it with BFS or DFS so every cell of that island is marked and never counted again.

Brute force first: There is no meaningfully slower correct approach; the common failure is re-counting the same island because cells were not marked visited.

Step-by-step approach

  1. Loop over every cell (r, c).
  2. If it is land and not yet visited, increase the island count.
  3. Start a BFS from it: mark it visited and push it on a queue.
  4. Pop cells, and push each in-bounds land neighbour (4 directions) that is not visited, marking it visited when you push it.
  5. When the queue empties, the whole island is marked; continue the scan.

Python solution

PYTHON 3tested
from collections import deque


def num_islands(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    seen = set()
    islands = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1" and (r, c) not in seen:
                islands += 1               # unseen land = a new island
                seen.add((r, c))
                q = deque([(r, c)])
                while q:                   # flood the whole island
                    x, y = q.popleft()
                    for nx, ny in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
                        if (0 <= nx < rows and 0 <= ny < cols
                                and grid[nx][ny] == "1" and (nx, ny) not in seen):
                            seen.add((nx, ny))
                            q.append((nx, ny))
    return islands

Complexity

TimeO(m·n)
SpaceO(m·n)

Each cell is scanned once and enqueued at most once, so the work is proportional to the m·n cells. The visited set (and the queue) can hold up to all cells.

Common mistakes

Frequently asked questions

What is the time and space complexity of Number of Islands?

O(m·n) time for an m by n grid, since each cell is visited a constant number of times. Space is O(m·n) in the worst case for the visited set and queue; overwriting land with '0' instead of a set saves the set but modifies the input.

BFS or DFS: which should I use?

Both count islands correctly. BFS with a queue avoids recursion-depth limits in Python, while recursive DFS is shorter to write. Mention the trade-off.

Can I solve it with Union-Find?

Yes. Start with one set per land cell and union each land cell with its land neighbours; the number of distinct sets is the answer. It shines when land is added over time, as in the Number of Islands II follow-up.

Is it okay to modify the input grid?

Sinking visited land by setting it to '0' saves memory and is common, but ask first. Some interviewers expect the input to stay unchanged.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Graphs & Grids Graph Search: BFS vs DFS lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.