Approach Summary
DFS/BFS from each unvisited land cell, marking all connected land as visited. Count how many times you start a DFS.
Practice Mode
2 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Depth-First Search (DFS) In-Place Flood Fill (Optimal) | O(M * N) | O(M * N) | Iterates through the grid, invoking recursive DFS to sink all connected land cells when a "1" is discovered. |
| 2 Approach 2: Breadth-First Search (BFS) Queue Traversal | O(M * N) | O(min(M, N)) | Level-by-level queue exploration of land components, ideal for deeply nested grids to avoid call stack overflow. |
Step 1: Baseline
Approach 1: Depth-First Search (DFS) In-Place Flood Fill (Optimal)
Time: O(M * N)
Space: O(M * N)
1. Loop over each cell `(i, j)` in the grid. 2. When `grid[i][j] == '1'` is hit, increment `numberOfIslands` by 1 and call `dfs(grid, i, j)`. 3. `dfs` checks boundary bounds and whether `grid[i][j] == '0'`. If invalid or water, it returns immediately. 4. Mark `grid[i][j] = '0'` to prevent visiting this land piece again. 5. Recursively call `dfs` on top, bottom, left, and right neighbors. 6. Return `numberOfIslands`.
Approach 1: Depth-First Search (DFS) In-Place Flood Fill (Optimal) Implementation
Approach 1: Depth-First Search (DFS) In-Place Flood Fill (Optimal)
class Solution {
public int numIslands(char[][] grid) {
int count = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == '1') {
count++;
dfs(grid, i, j);
}
}
}
return count;
}
void dfs(char[][] g, int r, int c) {
if (r < 0 || c < 0 || r >= g.length || c >= g[0].length || g[r][c] == '0') return;
g[r][c] = '0';
dfs(g, r + 1, c); dfs(g, r - 1, c); dfs(g, r, c + 1); dfs(g, r, c - 1);
}
}class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int count = 0;
for (int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[0].size(); j++) {
if (grid[i][j] == '1') {
count++;
dfs(grid, i, j);
}
}
}
return count;
}
void dfs(vector<vector<char>>& g, int r, int c) {
if (r < 0 || c < 0 || r >= g.size() || c >= g[0].size() || g[r][c] == '0') return;
g[r][c] = '0';
dfs(g, r + 1, c); dfs(g, r - 1, c); dfs(g, r, c + 1); dfs(g, r, c - 1);
}
};class Solution:
def numIslands(self, grid: list[list[str]]) -> int:
if not grid: return 0
m, n = len(grid), len(grid[0])
count = 0
def dfs(r, c):
if r < 0 or r >= m or c < 0 or c >= n or grid[r][c] == '0':
return
grid[r][c] = '0'
for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
dfs(r + dr, c + dc)
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
count += 1
dfs(i, j)
return countvar numIslands = function(grid) {
if (!grid.length) return 0;
const m = grid.length, n = grid[0].length;
let count = 0;
function dfs(r, c) {
if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] === '0') return;
grid[r][c] = '0';
dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1);
}
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === '1') {
count++;
dfs(i, j);
}
}
}
return count;
}; Step 2: Most Optimized
Approach 2: Breadth-First Search (BFS) Queue Traversal
Time: O(M * N)
Space: O(min(M, N))
1. Whenever a '1' is encountered, increment island count and enqueue coordinates `(r, c)`. 2. Mark `grid[r][c] = '0'` immediately upon enqueuing to prevent duplicate queue additions. 3. Dequeue cell `(currR, currC)` and check all 4 neighbors. 4. If a neighbor is within bounds and equals '1', set it to '0' and enqueue it. 5. Max queue size is bounded by the perimeter of the component, which is at most O(min(M, N)).
Approach 2: Breadth-First Search (BFS) Queue Traversal Implementation
Approach 2: Breadth-First Search (BFS) Queue Traversal
class Solution {
public int numIslands(char[][] grid) {
int m = grid.length, n = grid[0].length, count = 0;
int[][] dirs = {{1,0}, {-1,0}, {0,1}, {0,-1}};
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') {
count++;
grid[i][j] = '0';
Queue<int[]> q = new ArrayDeque<>();
q.add(new int[]{i, j});
while (!q.isEmpty()) {
int[] curr = q.poll();
for (int[] d : dirs) {
int nr = curr[0] + d[0], nc = curr[1] + d[1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == '1') {
grid[nr][nc] = '0';
q.add(new int[]{nr, nc});
}
}
}
}
}
}
return count;
}
}class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int m = grid.size(), n = grid[0].size(), count = 0;
int dirs[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') {
count++;
grid[i][j] = '0';
queue<pair<int, int>> q;
q.push({i, j});
while (!q.empty()) {
auto [r, c] = q.front(); q.pop();
for (auto& d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == '1') {
grid[nr][nc] = '0';
q.push({nr, nc});
}
}
}
}
}
}
return count;
}
};from collections import deque
class Solution:
def numIslands(self, grid: list[list[str]]) -> int:
if not grid: return 0
m, n = len(grid), len(grid[0])
count = 0
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
count += 1
grid[i][j] = '0'
q = deque([(i, j)])
while q:
r, c = q.popleft()
for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == '1':
grid[nr][nc] = '0'
q.append((nr, nc))
return countvar numIslands = function(grid) {
if (!grid.length) return 0;
const m = grid.length, n = grid[0].length;
let count = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === '1') {
count++;
grid[i][j] = '0';
const q = [[i, j]];
while (q.length > 0) {
const [r, c] = q.shift();
for (const [dr, dc] of [[1,0], [-1,0], [0,1], [0,-1]]) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] === '1') {
grid[nr][nc] = '0';
q.push([nr, nc]);
}
}
}
}
}
}
return count;
};Edge Cases to Watch
- Empty grid or grid with empty rows — return 0
- All water ('0') — no islands found, return 0
- All land ('1') — single giant island, return 1
- Diagonal land cells — diagonal connections do NOT form an island in 4-directional connectivity
Algorithmic Pattern
View Pattern Guide →
Master the Queue / BFS Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Queue / BFS pattern.
Framework: Queue / BFS • Interview Prep: Tested at FAANG •
Explore all Queue / BFS problems & invariants →
How to Recognize This Pattern
- Count connected components in grid
- Flood fill
Complexity Analysis
Time Complexity
O(m × n)
Space Complexity
O(m × n)
Tags
Array DFS BFS Matrix Union Find
Frequently Asked Questions
What is the optimal time and space complexity for Number of Islands?
The optimal solution for Number of Islands achieves O(m × n) runtime complexity and requires O(m × n) auxiliary space. Time Complexity is O(M * N) where M is the number of rows and N is the number of columns. Each cell in the grid is visited at most twice (once in the outer loops and once during the flood-fill). Space Complexity is O(M * N) in the worst case (e.g. a grid completely filled with land) for the DFS recursion stack or BFS queue.
How do I identify that Number of Islands requires the Queue / BFS pattern?
In technical interviews, look for key problem signals: Count connected components in grid; Flood fill. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Queue / BFS strategy.
What critical edge cases must be handled in Number of Islands?
Essential edge cases to verify include: Empty grid or grid with empty rows — return 0; All water ('0') — no islands found, return 0; All land ('1') — single giant island, return 1; Diagonal land cells — diagonal connections do NOT form an island in 4-directional connectivity. Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Number of Islands?
Number of Islands is a Medium-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Amazon, Google, Facebook, Microsoft.