Skip to main content
Talentd

Number of Islands - Solution & Explanation

MediumArrayDepth-First SearchBreadth-First SearchUnion Find37 min readAsked at: Amazon, Microsoft, Apple +83
Practice this problem

Problem Statement

Given an m x n 2D binary grid grid which represents a 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.

 

Example 1:

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

Example 2:

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

 

Constraints:

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

Approach Overview

Problem Overview: You are given an m x n grid of characters where '1' represents land and '0' represents water. Islands are formed by connecting adjacent land cells horizontally or vertically. The task is to count how many distinct islands exist in the grid.

Approach 1: Depth-First Search (DFS) Traversal (Time: O(m*n), Space: O(m*n))

This problem reduces to counting connected components in a grid. Iterate through every cell of the matrix. When you encounter a land cell '1', you've discovered a new island. Run a DFS from that cell and recursively visit all connected land cells (up, down, left, right), marking them as visited by turning them into '0'. This prevents counting the same island again. Each cell is visited at most once, so the traversal takes linear time relative to the number of cells. DFS is simple to implement and works naturally with recursion when exploring neighbors in a depth-first search pattern.

Approach 2: Breadth-First Search (BFS) Traversal (Time: O(m*n), Space: O(m*n))

BFS solves the same connected-component problem but explores the grid level by level using a queue. When a '1' is found, push it into a queue and repeatedly pop cells while adding all valid neighboring land cells. Mark each visited cell as water to avoid revisiting. BFS avoids recursion depth limits and is often preferred in languages where recursion stacks are shallow. The algorithm still scans every cell once, giving O(m*n) time complexity. This method directly uses breadth-first search on a matrix grid to flood-fill each island.

Approach 3: Union Find (Disjoint Set) (Time: O(m*n * α(n)), Space: O(m*n))

Union Find models each land cell as a node in a disjoint set. Iterate through the grid and union adjacent land cells so they belong to the same set. Initially, every land cell is its own component. When two neighboring land cells are discovered, perform a union operation to merge their sets. After processing the grid, the number of unique parents represents the number of islands. Path compression and union-by-rank keep operations nearly constant time. This method is useful when connectivity queries appear frequently and highlights how Union Find can track components efficiently.

Recommended for interviews: DFS or BFS traversal. Both clearly demonstrate understanding of grid traversal and connected components. DFS is typically the fastest to implement during interviews. BFS is equally valid and avoids recursion depth concerns. Union Find shows deeper algorithm knowledge but usually adds unnecessary complexity for this specific problem.

Approach 1: DFS Approach

This approach uses Depth-First Search (DFS) to explore the grid. We iterate over each cell in the grid, and every time we find an unvisited '1', it indicates the discovery of a new island. We then perform DFS from that cell to mark all the connected '1's as visited, effectively marking the entire island.

The function dfs is responsible for marking connected '1's as visited by changing them to '0'. The numIslands function traverses each cell in the grid, and upon finding a '1', it increments the count and triggers a DFS from that cell to mark the entire island.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m*n) where m is the number of rows and n is the number of columns since each cell is visited once.
Space Complexity: O(m*n) in the worst case due to the recursion stack used by DFS.

Try this approach in the editor →

Approach 2: BFS Approach

This approach uses Breadth-First Search (BFS) to traverse the grid. Similar to DFS, we treat each '1' as a node in a graph. On encountering a '1', we initiate a BFS to explore all connected '1's (island nodes) by utilizing a queue for the frontier, marking them in-place as visited.

This C implementation utilizes a queue for BFS to explore and mark connected components of each found '1'. An auxiliary structure QueueNode is used to keep track of cell indices being explored. BFS propagates through the nodes layer by layer until the entire island is marked.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m*n), where m and n are rows and columns.#
Space Complexity: O(min(m, n)) due to the queue storage in BFS.

Try this approach in the editor →

Approach 3: DFS

We can use depth-first search (DFS) to traverse each island. We iterate through each cell (i, j) in the grid. If the cell's value is '1', it means we have found a new island. We can start a DFS from this cell, marking all connected land cells as '0' to avoid duplicate counting. Each time we find a new island, we increment the island count by 1.

The time complexity is O(m times n), and the space complexity is O(m times n). Where m and n are the number of rows and columns in the grid, respectively.

Code

PythonJavaC++GoTypeScriptRustC#

Python

Java

C++

Go

TypeScript

Rust

C#

Try this approach in the editor →

Approach 4: BFS

We can also use breadth-first search (BFS) to traverse each island. We iterate through each cell (i, j) in the grid. If the cell's value is '1', it means we have found a new island. We can start a BFS from this cell, marking all connected land cells as '0' to avoid duplicate counting. Each time we find a new island, we increment the island count by 1.

The specific BFS process is as follows:

  1. Enqueue the starting cell (i, j) and mark its value as '0'.
  2. While the queue is not empty, perform the following operations:
    • Dequeue a cell p.
    • Iterate through the four adjacent cells (x, y) of p. If (x, y) is within the grid bounds and its value is '1', enqueue it and mark its value as '0'.

The time complexity is O(m times n), and the space complexity is O(m times n). Where m and n are the number of rows and columns in the grid, respectively.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Approach 5: Union-Find

We can use the Union-Find data structure to solve this problem. We traverse each cell (i, j) in the grid, and if the cell's value is '1', we merge it with adjacent land cells. Finally, we count the number of distinct root nodes in the Union-Find structure, which represents the number of islands.

The time complexity is O(m times n times log (m times n)), and the space complexity is O(m times n). Where m and n are the number of rows and columns in the grid, respectively.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
DFS Approach

Time Complexity: O(m*n) where m is the number of rows and n is the number of columns since each cell is visited once.
Space Complexity: O(m*n) in the worst case due to the recursion stack used by DFS.

BFS Approach

Time Complexity: O(m*n), where m and n are rows and columns.#
Space Complexity: O(min(m, n)) due to the queue storage in BFS.

DFS—
BFS—
Union-Find—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Depth-First Search (DFS)O(m*n)O(m*n)Most common interview solution. Simple recursive traversal of connected land cells.
Breadth-First Search (BFS)O(m*n)O(m*n)Preferred when avoiding recursion depth limits or when using iterative queue traversal.
Union Find (Disjoint Set)O(m*n * α(n))O(m*n)Useful when multiple connectivity queries are required or when demonstrating disjoint-set techniques.

Video Solution

LeetCode Number of Islands Solution Explained - Java • Nick White • 553,152 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Number of Islands easy or hard?
Number of Islands is generally classified as a medium difficulty problem. The logic is straightforward once you recognize it as a connected-components problem in a grid, but beginners may struggle with grid traversal and marking visited cells correctly.
How to solve Number of Islands in O(n)?
Treat the grid as a graph and run DFS or BFS whenever an unvisited land cell appears. The traversal marks all connected land cells as visited so they aren't counted again. Because each cell is processed once, the algorithm runs in O(m*n) time, which is linear relative to the grid size.
What is the best approach for Number of Islands?
Depth-First Search (DFS) or Breadth-First Search (BFS) is the most common approach. Both treat the grid as a graph and count connected components of land cells. Each time a '1' is found, a traversal marks all connected cells as visited. The overall time complexity is O(m*n) because each cell is processed once.
What data structure is used in Number of Islands?
The problem primarily uses graph traversal data structures. DFS uses the recursion stack, while BFS uses a queue to explore neighbors. Some implementations also use the Union Find (Disjoint Set) structure to group connected land cells into components.
What is the time complexity of Number of Islands?
The optimal time complexity is O(m*n), where m and n are the grid dimensions. Every cell is visited at most once during DFS or BFS traversal. Space complexity is O(m*n) in the worst case due to recursion stack or queue storage.
Number of Islands Python or Java solution approach?
Python and Java implementations typically use DFS or BFS. The grid is scanned cell by cell, and whenever a '1' appears, a traversal marks all adjacent land cells as visited. Both languages achieve O(m*n) time complexity with either recursion (DFS) or a queue-based BFS.
Is Number of Islands asked at Google, Amazon, or Meta?
Number of Islands frequently appears in interviews at companies like Amazon, Google, Meta, and Microsoft. It tests understanding of graph traversal, grid exploration, and connected components. Variants such as Number of Islands II or dynamic island counting are also common follow-ups.

Ready to solve this problem?

Practice Number of Islands with our built-in code editor and test cases.

Practice on FleetCode
Previous

Battleships in a Board

Next

Count Islands With Total Value Divisible by K