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.lengthn == grid[i].length1 <= m, n <= 300grid[i][j] is '0' or '1'.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.
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.
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.
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.
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.
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.
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:
(i, j) and mark its value as '0'.p.(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.
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.
| Approach | Complexity |
|---|---|
| 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. |
| BFS Approach | Time Complexity: O(m*n), where m and n are rows and columns.# |
| DFS | — |
| BFS | — |
| Union-Find | — |
| Approach | Time | Space | When 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. |
G-8. Number of Islands | Number of Connected Components in Matrix | C++ | Java • take U forward • 595,528 views views
Watch 9 more video solutions →Practice Number of Islands with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor