Number of Islands | Leetcode 200 | Explained using BFS and DFS

Learn how to count the number of islands (leetcode 200) in a 2-D grid using both Breadth-First Search (BFS) and Depth-First Search (DFS). This beginner-friendly guide shows a small example, fully-commented Python code, and clear time-complexity analysis.

Here’s the [Problem Link] to begin with.

What the Question Says — with a Small Example

You get a 2-D grid of characters:

'1'  = land
'0'  = water

Find how many separate islands of '1' exist.
Cells are connected only up, down, left, right (no diagonals).

Example Grid

1 1 0 0
1 0 0 1
0 0 1 1
0 0 0 0

Islands:

1. Cells (0,0) and (0,1) and (1,0)
2. Cell (1,3)
3. Cells (2,2) and (2,3)

Answer = 3.

Below are two ways to solve it with the code you gave, one uses BFS, the other DFS.

Also read about the Python Program to to count the number of distinct islands.

1) Breadth-First Search (BFS)

from collections import deque

class Solution:
    def bfs(self, i, j, visited, grid):
        rows = len(grid)
        cols = len(grid[0])
        queue = deque()
        queue.append((i, j))
        visited[i][j] = 1                # mark start cell

        while len(queue) != 0:
            x, y = queue.popleft()
            # explore 4-directional neighbours
            for xx, yy in [(-1, 0), (0, -1), (0, 1), (1, 0)]:
                new_i, new_j = x + xx, y + yy
                # skip out-of-bounds
                if new_i < 0 or new_j < 0 or new_i >= rows or new_j >= cols:
                    continue
                # skip water
                if grid[new_i][new_j] == "0":
                    continue
                # skip already-seen land
                if visited[new_i][new_j] == 1:
                    continue
                visited[new_i][new_j] = 1
                queue.append((new_i, new_j))

    def numIslands(self, grid: List[List[str]]) -> int:
        count = 0
        rows = len(grid)
        cols = len(grid[0])
        visited = [[0 for _ in range(cols)] for _ in range(rows)]

        for r in range(rows):
            for c in range(cols):
                # new island found
                if grid[r][c] == "1" and visited[r][c] == 0:
                    count += 1
                    self.bfs(r, c, visited, grid)   # flood-fill it
        return count

How BFS Works?

1. Loop through every cell.
   • When we hit an unvisited land cell ('1'), we found a new island → count += 1.
2. Start a queue from that cell.
   • Mark it visited, then repeatedly pop from the queue.
   • Push its up / down / left / right neighbours if they are land and not visited.
3. When queue empties, the whole island is marked.
   • Continue scanning the grid for the next unvisited '1'.

Why BFS?
It uses a queue to explore level-by-level, but here the main goal is simply to mark everything reachable from the start land cell.

Time Complexity: O(R × C) – each cell visited at most once.
Space Complexity: O(R × C) in worst case for visited + queue.

2) Depth-First Search (DFS)

class Solution:
    def dfs(self, i, j, visited, grid):
        # stop conditions
        if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]):
            return
        if grid[i][j] == "0":
            return
        if visited[i][j] == 1:
            return

        visited[i][j] = 1          # mark current land

        # recurse in 4 directions
        self.dfs(i + 1, j, visited, grid)
        self.dfs(i - 1, j, visited, grid)
        self.dfs(i, j - 1, visited, grid)
        self.dfs(i, j + 1, visited, grid)

    def numIslands(self, grid: List[List[str]]) -> int:
        count = 0
        rows = len(grid)
        cols = len(grid[0])
        visited = [[0 for _ in range(cols)] for _ in range(rows)]

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == "1" and visited[r][c] == 0:
                    count += 1
                    self.dfs(r, c, visited, grid)   # flood-fill recursively
        return count

How DFS Works in Plain English

1. Scan every cell.
   • When we meet an unvisited '1', increment island count.
2. Call dfs on that cell.
   • Mark this land visited.
   • Recursively call dfs on each of its four neighbours.
   • The recursion keeps going until the whole island is marked.
3. Return to the outer loop and keep looking for the next unvisited land cell.

Why DFS?
Recursion uses the call stack to “dive” deep into one direction before backtracking—handy for flood-fill problems.

Time Complexity: O(R × C) – same reason as BFS.
Space Complexity:

• O(R × C) for visited.
• Plus recursion stack up to O(R × C) in worst case (if the island is one big snake).

Which One to Pick?

• BFS uses an explicit queue; memory stays proportional to the island’s “frontier.”
• DFS is often shorter to write but risks deep recursion (Python’s default recursion limit) on large grids.

Both methods correctly count islands in linear time over the grid size. Use whichever style you are more comfortable with.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.