How do you solve Number of Islands?

Iterate over every cell in the grid. When an unvisited land cell ('1') is found, initiate a DFS to mark all connected land cells as visited. Increment the island count by one for each such DFS initiation. The DFS recursively explores neighbors in four directions, stopping at water, visited cells, or out-of-bounds indices. This guarantees each island is counted exactly once.

What pattern does Number of Islands use?

The Pattern: DFS (Connected Components in Grid) The Heuristic: When counting islands or connected regions in a grid, use DFS to fully explore and mark each connected component starting from an unvisited land cell, ensuring no double counting and linear time complexity.

Number of Islands — DFS

Q: What is the time complexity of Number of Islands?

O(m * n). Each cell is visited at most once during the DFS traversal or the main iteration. The DFS explores neighbors recursively but never revisits visited cells, resulting in linear time proportional to the grid size.

Problem

Given a 2D grid map of '1's (land) and '0's (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

m == grid.length
n == grid[i].length
1 ≤ m, n ≤ 300
grid[i][j] is '0' or '1'

Example

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

Output: 3

The grid contains three islands. The first island is formed by the top-left four '1's connected horizontally and vertically. The second island is the single '1' at position (2,2). The third island consists of the two connected '1's at the bottom-right corner. The DFS explores each island fully, marking visited land cells to avoid double counting.

Approach

Straightforward Solution

A brute-force approach would scan the grid and for each '1' found, perform a DFS or BFS to mark all connected '1's as visited, incrementing the island count. Without marking visited cells, the algorithm would count the same island multiple times.

Core Observation

Islands are connected components of '1's in a grid, where connectivity is defined horizontally and vertically. The problem reduces to counting connected components in a grid graph.

Path to Optimal

Preview

The key insight is to use DFS to explore all connected land cells starting from an unvisited '1'. By marking visited cells, the algorithm avoids revisiting and recounting the same island…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Iterate over every cell in the grid. When an unvisited land cell ('1') is found, initiate a DFS to mark all connected land cells as visited…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(m * n)

Each cell is visited at most once during the DFS traversal or the main iteration. The DFS explores neighbors recursively but never revisits visited cells, resulting in linear time proportional to the grid size.

Space

O(m * n)

The visited set can store up to all cells in the grid in the worst case (all land). The recursion stack depth can be up to O(m * n) in the worst case of a single large island, which is acceptable for this problem.

Solution

Python

1class Solution:
  def numIslands(self, grid: list[list[str]]) -> int:
      if not grid:
          return 0
      
      ROWS, COLS = len(grid), len(grid[0])
      visited = set()
      islands = 0
9
      def dfs(r, c):
          if (r not in range(ROWS) or
              c not in range(COLS) or
              grid[r][c] == '0' or
              (r, c) in visited):
              return
          
          visited.add((r, c))
          dfs(r + 1, c)
          dfs(r - 1, c)
          dfs(r, c + 1)
          dfs(r, c - 1)
22
      for r in range(ROWS):
          for c in range(COLS):
              if grid[r][c] == '1' and (r, c) not in visited:
                  dfs(r, c)
                  islands += 1
      
      return islands

Step-by-Step Solution

1

Handle Empty Grid Edge Case

3if not grid:
4    return 0

Objective

To immediately return 0 if the input grid is empty, as no islands can exist.

Key Insight

An empty grid means there are no cells to explore, so the number of islands is trivially zero. Handling this edge case upfront avoids errors in subsequent code that assumes a non-empty grid.

Interview Quick-Check

State & Boundaries

Check if the grid is empty before accessing its dimensions to prevent index errors.

2

Initialize Grid Dimensions, Visited Set, and Island Counter

To prepare the necessary variables for grid traversal and tracking visited land cells.

3

Recursively Explore Connected Land Cells via DFS

To perform a depth-first search that marks all land cells connected to the starting cell as visited.

4

Iterate Over Grid to Identify and Count Islands

To scan every cell in the grid and initiate DFS for each unvisited land cell, incrementing the island count accordingly.

5

Return Total Number of Islands Found

To output the final count of distinct islands after full grid traversal.

4 more steps with full analysis available on Pro.

Line Analysis

This solution has 7 Critical lines interviewers watch for.

Line 14 Critical

(r, c) in visited):

Check if the current cell has already been visited.

Avoids revisiting cells, which prevents infinite recursion and double counting of land cells.

Line 17 Critical

visited.add((r, c))

Mark the current cell as visited.

Marking before recursive calls prevents cycles and ensures each land cell is processed exactly once.

Line 26 Critical

dfs(r, c)

Invoke DFS to explore the entire island connected to the current cell.

This call fully explores and marks all connected land cells, ensuring the island is counted once.

Full line-by-line criticality + rationale for all 22 lines available on Pro.

Test Your Understanding

Why is it necessary to mark cells as visited during DFS when counting islands?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Number of Islands from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Number of Islands drill

or drill a free problem

1	`class Solution:`
2	`def numIslands(self, grid: list[list[str]]) -> int:`
3	`if not grid:`
4	`return 0`
5
6	`ROWS, COLS = len(grid), len(grid[0])`
7	`visited = set()`
8	`islands = 0`
9
10	`def dfs(r, c):`
11	`if (r not in range(ROWS) or`
12	`c not in range(COLS) or`
13	`grid[r][c] == '0' or`
14	`(r, c) in visited):`
15	`return`
16
17	`visited.add((r, c))`
18	`dfs(r + 1, c)`
19	`dfs(r - 1, c)`
20	`dfs(r, c + 1)`
21	`dfs(r, c - 1)`
22
23	`for r in range(ROWS):`
24	`for c in range(COLS):`
25	`if grid[r][c] == '1' and (r, c) not in visited:`
26	`dfs(r, c)`
27	`islands += 1`
28
29	`return islands`