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'.The key idea in #200 Number of Islands is to treat the grid as a graph where each cell is a node connected to its neighboring land cells. Whenever you encounter a cell with value '1', it represents unvisited land and can be the starting point of a new island. From this cell, explore all connected land cells using Depth-First Search (DFS) or Breadth-First Search (BFS), marking them as visited to avoid counting them again.
Each traversal effectively "floods" the island by visiting all adjacent land cells (up, down, left, right). Another alternative approach uses Union-Find (Disjoint Set), where neighboring land cells are merged into the same set, and the number of unique sets represents the number of islands.
Both DFS and BFS iterate through every grid cell at most once, giving an efficient solution. Understanding grid traversal and visited tracking is crucial for solving this problem efficiently.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| DFS / BFS Traversal | O(m × n) | O(m × n) |
| Union-Find (Disjoint Set) | O(m × n · α(n)) | O(m × n) |
Nick White
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.
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.
1var numIslands = function(grid) {
2 function dfs(grid, r, c) {
3 if (r < 0 || c <The JavaScript solution leverages a classic DFS function dfs to explore the grid and perform in-place modification to mark visited cells. As it iterates through the grid, whenever it encounters '1', it initiates DFS to mark the whole island, counting it.
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.
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.
1#include <queue>
using namespace std;
void bfs(vector<vector<char>>& grid, int r, int c) {
queue<pair<int, int>> q;
q.push({r, c});
grid[r][c] = '0';
vector<vector<int>> directions {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
while (!q.empty()) {
int cr = q.front().first;
int cc = q.front().second;
q.pop();
for (vector<int>& dir : directions) {
int nr = cr + dir[0], nc = cc + dir[1];
if (nr >= 0 && nr < grid.size() && nc >= 0 && nc < grid[0].size() && grid[nr][nc] == '1') {
grid[nr][nc] = '0';
q.push({nr, nc});
}
}
}
}
int numIslands(vector<vector<char>>& grid) {
int numIslands = 0;
for (int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[i].size(); j++) {
if (grid[i][j] == '1') {
bfs(grid, i, j);
numIslands++;
}
}
}
return numIslands;
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Number of Islands is a very popular interview question at FAANG and other top tech companies. It tests understanding of graph traversal, grid processing, and recursion or queue-based BFS. Variations of this problem are also commonly asked.
Graphs and grids are best handled using traversal techniques like DFS with recursion or BFS with a queue. A visited structure or in-place marking is used to prevent revisiting cells. Alternatively, a Union-Find structure can group connected land cells efficiently.
The most common optimal approach is using DFS or BFS to traverse the grid. Each time a land cell is found, a traversal explores all connected land cells and marks them as visited. This ensures every island is counted exactly once.
Marking cells as visited ensures the same land cell is not counted multiple times. During DFS or BFS traversal, all connected land cells of an island are explored and marked. This guarantees that each island contributes only one count to the final answer.
The C++ solution employs a std::queue to facilitate BFS over '1's in the grid. When a '1' is encountered, we launch BFS, exploring all connected '1's by marking them and enqueuing adjacent unvisited ones, effectively dedicating BFS for the whole discovered island.