Introduction

Number of Islands is one of the most popular BFS and DFS interview problems.

You are given:

grid[][]

Goal:

Count the number of islands.

Island means:

Connected group of 1s.

Movement:

UpDown
Left
Right

Example

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

Output:

 3

Key Observation

Whenever we find:

grid[i][j] == '1'

We discovered:

A new island.

Perform:

DFS or BFS

to visit the entire island.

Algorithm

1. Traverse grid.
2. Find land cell.
3. Increase island count.
4. Run DFS/BFS.
5. Mark all connected land.

Dry Run

Input:

11000
11000
00100
00011

Island Count:

Island 1
Island 2
Island 3

Answer:

3

Approach 1 : DFS

Explanation

For every land cell:

  1. Visit current cell.
  2. Mark visited.
  3. Explore 4 directions.
  4. Continue recursively.

Practice

Complexity Analysis

DFSTime Complexity: O(m × n)
Space Complexity: O(m × n)

BFS
Time Complexity: O(m × n)
Space Complexity: O(m × n)

Why This Problem is Important

  • BFS
  • DFS
  • Graph Traversal
  • Matrix Traversal
  • Connected Components

Common Beginner Mistakes

  • Not marking visited cells
  • Visiting diagonals
  • Boundary errors
  • Double counting islands
  • Infinite recursion

Interview Tip

Always explain:

Every time we find an unvisited land cell,we discovered a new island.

Then run DFS/BFS to mark the entire island.

Related Questions

  • Flood Fill
  • Surrounded Regions
  • Pacific Atlantic Water Flow
  • Number of Provinces
  • Rotting Oranges

Final Takeaway

Number of Islands is the foundation of BFS and DFS on grids.

It teaches:

  • Graph Traversal
  • Connected Components
  • Matrix DFS
  • Matrix BFS

Mastering Number of Islands makes most grid-based graph problems significantly easier.