Number of Islands

🎯

Number of Islands

mediumGRAPHAmazonFacebookGoogle

Imagine you are analyzing satellite images of an archipelago to count how many separate islands exist in a vast ocean grid.

💡 This problem is a classic example of exploring connected components in a grid using graph traversal techniques. Beginners often struggle because the grid is not explicitly a graph, and they must learn to treat adjacent cells as graph edges and mark visited nodes to avoid counting islands multiple times.

📋

Problem Statement

Given a 2D grid map of '1's (land) and '0's (water), count 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.

m == grid.lengthn == grid[i].length1 ≤ m, n ≤ 300grid[i][j] is '0' or '1'

💡

Example

Input"[[\"1\",\"1\",\"1\",\"1\",\"0\"],[\"1\",\"1\",\"0\",\"1\",\"0\"],[\"1\",\"1\",\"0\",\"0\",\"0\"],[\"0\",\"0\",\"0\",\"0\",\"0\"]]"

Output1

All connected '1's form one big island.

Input"[[\"1\",\"1\",\"0\",\"0\",\"0\"],[\"1\",\"1\",\"0\",\"0\",\"0\"],[\"0\",\"0\",\"1\",\"0\",\"0\"],[\"0\",\"0\",\"0\",\"1\",\"1\"]]"

Output3

There are three separate islands in the grid.

• Grid with all water → 0 islands
• Grid with all land → 1 island
• Grid with single cell land → 1 island
• Grid with single cell water → 0 islands

⚠️

Common Mistakes

Not marking visited cells

Infinite recursion or counting the same island multiple times

✅ Use a visited set or mark cells as visited during traversal

Incorrect boundary checks

Index out of range errors or missing islands at edges

✅ Always check row and column indices before accessing grid cells

Counting water cells as islands

Incorrect island count

✅ Only start traversal on cells with '1' (land)

Modifying input grid when not allowed

Unexpected side effects or failing tests

✅ Use a separate visited structure if input must remain unchanged

Using recursion without considering stack limits

Stack overflow on large grids

✅ Use BFS or iterative DFS to avoid deep recursion

🧠

Brute Force (DFS with Visited Set)

💡 Starting with brute force DFS helps understand the problem as exploring each cell and marking connected lands. It is intuitive and lays the foundation for optimized approaches.

Intuition

Traverse every cell; when land is found, perform DFS to mark all connected land cells as visited, then increment island count.

Algorithm

1. Initialize island count to zero.
2. Iterate over each cell in the grid.
3. If the cell is land and not visited, perform DFS to mark all connected land cells.
4. Increment island count after each DFS call.

💡 The main challenge is to correctly mark visited cells to avoid recounting and to explore all four directions safely.

</>

Code

from typing import List

def numIslands(grid: List[List[str]]) -> int:
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    visited = set()

    def dfs(r, c):
        if (r < 0 or c < 0 or r >= rows or c >= cols or
            grid[r][c] == '0' or (r, c) in visited):
            return
        visited.add((r, c))
        dfs(r+1, c)
        dfs(r-1, c)
        dfs(r, c+1)
        dfs(r, c-1)

    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1' and (r, c) not in visited:
                dfs(r, c)
                count += 1
    return count

# Driver code
if __name__ == '__main__':
    grid = [
        ["1","1","0","0","0"],
        ["1","1","0","0","0"],
        ["0","0","1","0","0"],
        ["0","0","0","1","1"]
    ]
    print(numIslands(grid))  # Expected output: 3

Line Notes

if not grid:Check for empty input to avoid errors.

visited = set()Track visited cells to prevent revisiting and infinite recursion.

def dfs(r, c):Define recursive DFS to explore connected land.

if (r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] == '0' or (r, c) in visited):Base case to stop recursion on water, out-of-bounds, or visited cells.

visited.add((r, c))Mark current cell as visited to avoid reprocessing.

dfs(r+1, c)Explore downward neighbor.

dfs(r-1, c)Explore upward neighbor.

dfs(r, c+1)Explore right neighbor.

dfs(r, c-1)Explore left neighbor.

for r in range(rows):Iterate over each row in the grid.

for c in range(cols):Iterate over each column in the grid.

if grid[r][c] == '1' and (r, c) not in visited:Start DFS only on unvisited land cells.

count += 1Increment island count after fully exploring one island.

import java.util.*;

public class NumberOfIslands {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        int rows = grid.length, cols = grid[0].length;
        boolean[][] visited = new boolean[rows][cols];
        int count = 0;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == '1' && !visited[r][c]) {
                    dfs(grid, visited, r, c);
                    count++;
                }
            }
        }
        return count;
    }

    private void dfs(char[][] grid, boolean[][] visited, int r, int c) {
        if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length ||
            grid[r][c] == '0' || visited[r][c]) return;
        visited[r][c] = true;
        dfs(grid, visited, r + 1, c);
        dfs(grid, visited, r - 1, c);
        dfs(grid, visited, r, c + 1);
        dfs(grid, visited, r, c - 1);
    }

    public static void main(String[] args) {
        NumberOfIslands solver = new NumberOfIslands();
        char[][] grid = {
            {'1','1','0','0','0'},
            {'1','1','0','0','0'},
            {'0','0','1','0','0'},
            {'0','0','0','1','1'}
        };
        System.out.println(solver.numIslands(grid)); // Expected output: 3
    }
}

Line Notes

if (grid == null || grid.length == 0) return 0;Handle empty or null input gracefully.

boolean[][] visited = new boolean[rows][cols];Track visited cells to avoid revisiting.

if (grid[r][c] == '1' && !visited[r][c]) {Start DFS only on unvisited land cells.

visited[r][c] = true;Mark current cell as visited to prevent cycles.

dfs(grid, visited, r + 1, c);Explore downward neighbor recursively.

dfs(grid, visited, r - 1, c);Explore upward neighbor recursively.

dfs(grid, visited, r, c + 1);Explore right neighbor recursively.

dfs(grid, visited, r, c - 1);Explore left neighbor recursively.

for (int r = 0; r < rows; r++) {Iterate over each row in the grid.

for (int c = 0; c < cols; c++) {Iterate over each column in the grid.

count++;Increment island count after DFS completes for one island.

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    void dfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int r, int c) {
        int rows = grid.size();
        int cols = grid[0].size();
        if (r < 0 || c < 0 || r >= rows || c >= cols ||
            grid[r][c] == '0' || visited[r][c]) return;
        visited[r][c] = true;
        dfs(grid, visited, r + 1, c);
        dfs(grid, visited, r - 1, c);
        dfs(grid, visited, r, c + 1);
        dfs(grid, visited, r, c - 1);
    }

    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty()) return 0;
        int rows = grid.size();
        int cols = grid[0].size();
        vector<vector<bool>> visited(rows, vector<bool>(cols, false));
        int count = 0;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == '1' && !visited[r][c]) {
                    dfs(grid, visited, r, c);
                    count++;
                }
            }
        }
        return count;
    }
};

int main() {
    Solution sol;
    vector<vector<char>> grid = {
        {'1','1','0','0','0'},
        {'1','1','0','0','0'},
        {'0','0','1','0','0'},
        {'0','0','0','1','1'}
    };
    cout << sol.numIslands(grid) << endl; // Expected output: 3
    return 0;
}

Line Notes

if (grid.empty()) return 0;Check for empty grid to avoid errors.

vector<vector<bool>> visited(rows, vector<bool>(cols, false));Initialize visited matrix to track explored cells.

if (grid[r][c] == '1' && !visited[r][c]) {Start DFS only on unvisited land cells.

visited[r][c] = true;Mark current cell visited to prevent revisiting.

dfs(grid, visited, r + 1, c);Explore downward neighbor recursively.

dfs(grid, visited, r - 1, c);Explore upward neighbor recursively.

dfs(grid, visited, r, c + 1);Explore right neighbor recursively.

dfs(grid, visited, r, c - 1);Explore left neighbor recursively.

for (int r = 0; r < rows; r++) {Iterate over all rows.

for (int c = 0; c < cols; c++) {Iterate over all columns.

count++;Increment island count after DFS completes.

var numIslands = function(grid) {
    if (!grid || grid.length === 0) return 0;
    const rows = grid.length, cols = grid[0].length;
    const visited = new Set();

    function dfs(r, c) {
        if (r < 0 || c < 0 || r >= rows || c >= cols ||
            grid[r][c] === '0' || visited.has(r + ',' + c)) return;
        visited.add(r + ',' + c);
        dfs(r + 1, c);
        dfs(r - 1, c);
        dfs(r, c + 1);
        dfs(r, c - 1);
    }

    let count = 0;
    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (grid[r][c] === '1' && !visited.has(r + ',' + c)) {
                dfs(r, c);
                count++;
            }
        }
    }
    return count;
};

// Test
const grid = [
    ['1','1','0','0','0'],
    ['1','1','0','0','0'],
    ['0','0','1','0','0'],
    ['0','0','0','1','1']
];
console.log(numIslands(grid)); // Expected output: 3

Line Notes

if (!grid || grid.length === 0) return 0;Guard clause for empty input.

const visited = new Set();Use a set to track visited cells uniquely.

if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] === '0' || visited.has(r + ',' + c)) return;Stop DFS on invalid or visited cells.

visited.add(r + ',' + c);Mark current cell visited to avoid cycles.

dfs(r + 1, c);Explore downward neighbor.

dfs(r - 1, c);Explore upward neighbor.

dfs(r, c + 1);Explore right neighbor.

dfs(r, c - 1);Explore left neighbor.

for (let r = 0; r < rows; r++) {Iterate over rows.

for (let c = 0; c < cols; c++) {Iterate over columns.

count++;Increment island count after DFS completes.

⏱

Complexity

TimeO(m*n)

SpaceO(m*n)

We visit each cell once, and DFS explores connected lands marking them visited. The visited set or matrix can grow up to m*n in worst case.

💡 For a 300x300 grid, this means up to 90,000 operations, which is efficient enough for interview constraints.

Interview Verdict: Accepted

This approach is accepted and efficient enough for typical interview constraints, making it a solid baseline solution.

🧠

BFS Approach (Queue-based Traversal)

💡 BFS is an alternative to DFS that uses a queue to explore neighbors level by level. It helps understand iterative graph traversal and can avoid recursion stack overflow.

Intuition

When land is found, use a queue to explore all connected land cells iteratively, marking them visited to count one island.

Algorithm

1. Initialize island count to zero.
2. Iterate over each cell in the grid.
3. If the cell is land and not visited, enqueue it and mark visited.
4. While the queue is not empty, dequeue a cell and enqueue all unvisited land neighbors.
5. Increment island count after fully exploring one island.

💡 The main difference from DFS is using a queue to explore neighbors iteratively rather than recursion.

</>

Code

from typing import List
from collections import deque

def numIslands(grid: List[List[str]]) -> int:
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    visited = set()
    count = 0

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1' and (r, c) not in visited:
                queue = deque()
                queue.append((r, c))
                visited.add((r, c))
                while queue:
                    row, col = queue.popleft()
                    for nr, nc in [(row+1,col),(row-1,col),(row,col+1),(row,col-1)]:
                        if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1' and (nr, nc) not in visited:
                            queue.append((nr, nc))
                            visited.add((nr, nc))
                count += 1
    return count

# Driver code
if __name__ == '__main__':
    grid = [
        ["1","1","0","0","0"],
        ["1","1","0","0","0"],
        ["0","0","1","0","0"],
        ["0","0","0","1","1"]
    ]
    print(numIslands(grid))  # Expected output: 3

Line Notes

from collections import dequeImport deque for efficient queue operations.

visited = set()Track visited cells to avoid revisiting.

if grid[r][c] == '1' and (r, c) not in visited:Start BFS only on unvisited land cells.

queue = deque()Initialize queue for BFS traversal.

queue.append((r, c))Enqueue starting cell of island.

while queue:Process cells until all connected lands are visited.

for nr, nc in [(row+1,col),(row-1,col),(row,col+1),(row,col-1)]:Check all four neighbors.

if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1' and (nr, nc) not in visited:Enqueue unvisited land neighbors.

count += 1Increment island count after BFS completes.

import java.util.*;

public class NumberOfIslands {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        int rows = grid.length, cols = grid[0].length;
        boolean[][] visited = new boolean[rows][cols];
        int count = 0;
        int[][] directions = {{1,0},{-1,0},{0,1},{0,-1}};
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == '1' && !visited[r][c]) {
                    Queue<int[]> queue = new LinkedList<>();
                    queue.offer(new int[]{r, c});
                    visited[r][c] = true;
                    while (!queue.isEmpty()) {
                        int[] cell = queue.poll();
                        for (int[] d : directions) {
                            int nr = cell[0] + d[0];
                            int nc = cell[1] + d[1];
                            if (nr >= 0 && nc >= 0 && nr < rows && nc < cols &&
                                grid[nr][nc] == '1' && !visited[nr][nc]) {
                                queue.offer(new int[]{nr, nc});
                                visited[nr][nc] = true;
                            }
                        }
                    }
                    count++;
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        NumberOfIslands solver = new NumberOfIslands();
        char[][] grid = {
            {'1','1','0','0','0'},
            {'1','1','0','0','0'},
            {'0','0','1','0','0'},
            {'0','0','0','1','1'}
        };
        System.out.println(solver.numIslands(grid)); // Expected output: 3
    }
}

Line Notes

boolean[][] visited = new boolean[rows][cols];Track visited cells to avoid revisiting.

int[][] directions = {{1,0},{-1,0},{0,1},{0,-1}};Store directions for neighbor exploration.

Queue<int[]> queue = new LinkedList<>();Initialize queue for BFS.

queue.offer(new int[]{r, c});Enqueue starting cell of island.

visited[r][c] = true;Mark starting cell visited.

while (!queue.isEmpty()) {Process all connected land cells.

if (nr >= 0 && nc >= 0 && nr < rows && nc < cols && grid[nr][nc] == '1' && !visited[nr][nc]) {Check valid unvisited land neighbors.

queue.offer(new int[]{nr, nc});Enqueue neighbor cells.

count++;Increment island count after BFS completes.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty()) return 0;
        int rows = grid.size(), cols = grid[0].size();
        vector<vector<bool>> visited(rows, vector<bool>(cols, false));
        int count = 0;
        vector<pair<int,int>> directions = {{1,0},{-1,0},{0,1},{0,-1}};
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == '1' && !visited[r][c]) {
                    queue<pair<int,int>> q;
                    q.push({r, c});
                    visited[r][c] = true;
                    while (!q.empty()) {
                        auto [row, col] = q.front(); q.pop();
                        for (auto& d : directions) {
                            int nr = row + d.first, nc = col + d.second;
                            if (nr >= 0 && nc >= 0 && nr < rows && nc < cols &&
                                grid[nr][nc] == '1' && !visited[nr][nc]) {
                                q.push({nr, nc});
                                visited[nr][nc] = true;
                            }
                        }
                    }
                    count++;
                }
            }
        }
        return count;
    }
};

int main() {
    Solution sol;
    vector<vector<char>> grid = {
        {'1','1','0','0','0'},
        {'1','1','0','0','0'},
        {'0','0','1','0','0'},
        {'0','0','0','1','1'}
    };
    cout << sol.numIslands(grid) << endl; // Expected output: 3
    return 0;
}

Line Notes

vector<vector<bool>> visited(rows, vector<bool>(cols, false));Track visited cells to avoid revisiting.

vector<pair<int,int>> directions = {{1,0},{-1,0},{0,1},{0,-1}};Store directions for neighbor exploration.

queue<pair<int,int>> q;Initialize queue for BFS traversal.

q.push({r, c});Enqueue starting cell of island.

visited[r][c] = true;Mark starting cell visited.

while (!q.empty()) {Process all connected land cells iteratively.

if (nr >= 0 && nc >= 0 && nr < rows && nc < cols && grid[nr][nc] == '1' && !visited[nr][nc]) {Check valid unvisited land neighbors.

q.push({nr, nc});Enqueue neighbor cells.

count++;Increment island count after BFS completes.

var numIslands = function(grid) {
    if (!grid || grid.length === 0) return 0;
    const rows = grid.length, cols = grid[0].length;
    const visited = new Set();
    const directions = [[1,0],[-1,0],[0,1],[0,-1]];
    let count = 0;

    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (grid[r][c] === '1' && !visited.has(r + ',' + c)) {
                const queue = [];
                queue.push([r, c]);
                visited.add(r + ',' + c);
                while (queue.length > 0) {
                    const [row, col] = queue.shift();
                    for (const [dr, dc] of directions) {
                        const nr = row + dr, nc = col + dc;
                        if (nr >= 0 && nc >= 0 && nr < rows && nc < cols &&
                            grid[nr][nc] === '1' && !visited.has(nr + ',' + nc)) {
                            queue.push([nr, nc]);
                            visited.add(nr + ',' + nc);
                        }
                    }
                }
                count++;
            }
        }
    }
    return count;
};

// Test
const grid = [
    ['1','1','0','0','0'],
    ['1','1','0','0','0'],
    ['0','0','1','0','0'],
    ['0','0','0','1','1']
];
console.log(numIslands(grid)); // Expected output: 3

Line Notes

const visited = new Set();Track visited cells uniquely to avoid revisiting.

const directions = [[1,0],[-1,0],[0,1],[0,-1]];Store directions for neighbor exploration.

const queue = [];Initialize queue for BFS traversal.

queue.push([r, c]);Enqueue starting cell of island.

visited.add(r + ',' + c);Mark starting cell visited.

while (queue.length > 0) {Process all connected land cells iteratively.

if (nr >= 0 && nc >= 0 && nr < rows && nc < cols && grid[nr][nc] === '1' && !visited.has(nr + ',' + nc)) {Check valid unvisited land neighbors.

queue.push([nr, nc]);Enqueue neighbor cells.

count++;Increment island count after BFS completes.

⏱

Complexity

TimeO(m*n)

SpaceO(m*n)

Each cell is visited once, and BFS explores neighbors using a queue. The visited set or matrix can grow up to m*n.

💡 For a 300x300 grid, this means up to 90,000 operations, which is efficient and avoids recursion stack issues.

Interview Verdict: Accepted

BFS is accepted and useful especially when recursion depth is a concern, demonstrating iterative graph traversal skills.

🧠

In-place DFS (Marking Visited by Modifying Grid)

💡 Instead of using extra space for visited tracking, we can mark visited land cells by changing their value in the grid. This reduces space usage and is a common interview optimization.

Intuition

When visiting a land cell, change it to water ('0') to mark it visited, then recursively explore neighbors to avoid revisiting.

Algorithm

1. Initialize island count to zero.
2. Iterate over each cell in the grid.
3. If the cell is land ('1'), perform DFS to mark connected lands as '0'.
4. Increment island count after each DFS call.

💡 Modifying the input grid in-place saves space but requires careful handling to avoid corrupting data.

</>

Code

from typing import List

def numIslands(grid: List[List[str]]) -> int:
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])

    def dfs(r, c):
        if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] == '0':
            return
        grid[r][c] = '0'  # mark visited by sinking island
        dfs(r+1, c)
        dfs(r-1, c)
        dfs(r, c+1)
        dfs(r, c-1)

    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                dfs(r, c)
                count += 1
    return count

# Driver code
if __name__ == '__main__':
    grid = [
        ["1","1","0","0","0"],
        ["1","1","0","0","0"],
        ["0","0","1","0","0"],
        ["0","0","0","1","1"]
    ]
    print(numIslands(grid))  # Expected output: 3

Line Notes

if not grid:Check for empty input to avoid errors.

def dfs(r, c):Recursive DFS to explore and mark connected lands.

if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] == '0':Stop recursion on invalid or water cells.

grid[r][c] = '0'Mark current land cell visited by sinking it.

dfs(r+1, c)Explore downward neighbor.

dfs(r-1, c)Explore upward neighbor.

dfs(r, c+1)Explore right neighbor.

dfs(r, c-1)Explore left neighbor.

for r in range(rows):Iterate over all rows.

for c in range(cols):Iterate over all columns.

if grid[r][c] == '1':Start DFS on unvisited land cells.

count += 1Increment island count after DFS completes.

public class NumberOfIslands {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        int rows = grid.length, cols = grid[0].length;
        int count = 0;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == '1') {
                    dfs(grid, r, c);
                    count++;
                }
            }
        }
        return count;
    }

    private void dfs(char[][] grid, int r, int c) {
        if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length || grid[r][c] == '0') return;
        grid[r][c] = '0'; // mark visited by sinking
        dfs(grid, r + 1, c);
        dfs(grid, r - 1, c);
        dfs(grid, r, c + 1);
        dfs(grid, r, c - 1);
    }

    public static void main(String[] args) {
        NumberOfIslands solver = new NumberOfIslands();
        char[][] grid = {
            {'1','1','0','0','0'},
            {'1','1','0','0','0'},
            {'0','0','1','0','0'},
            {'0','0','0','1','1'}
        };
        System.out.println(solver.numIslands(grid)); // Expected output: 3
    }
}

Line Notes

if (grid == null || grid.length == 0) return 0;Handle empty input gracefully.

if (grid[r][c] == '1') {Start DFS on unvisited land cells.

grid[r][c] = '0';Mark visited by sinking the island cell.

if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length || grid[r][c] == '0') return;Stop recursion on invalid or water cells.

dfs(grid, r + 1, c);Explore downward neighbor.

dfs(grid, r - 1, c);Explore upward neighbor.

dfs(grid, r, c + 1);Explore right neighbor.

dfs(grid, r, c - 1);Explore left neighbor.

count++;Increment island count after DFS completes.

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    void dfs(vector<vector<char>>& grid, int r, int c) {
        int rows = grid.size();
        int cols = grid[0].size();
        if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] == '0') return;
        grid[r][c] = '0'; // mark visited by sinking
        dfs(grid, r + 1, c);
        dfs(grid, r - 1, c);
        dfs(grid, r, c + 1);
        dfs(grid, r, c - 1);
    }

    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty()) return 0;
        int rows = grid.size();
        int cols = grid[0].size();
        int count = 0;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == '1') {
                    dfs(grid, r, c);
                    count++;
                }
            }
        }
        return count;
    }
};

int main() {
    Solution sol;
    vector<vector<char>> grid = {
        {'1','1','0','0','0'},
        {'1','1','0','0','0'},
        {'0','0','1','0','0'},
        {'0','0','0','1','1'}
    };
    cout << sol.numIslands(grid) << endl; // Expected output: 3
    return 0;
}

Line Notes

if (grid.empty()) return 0;Check for empty input to avoid errors.

if (grid[r][c] == '1') {Start DFS on unvisited land cells.

grid[r][c] = '0';Mark visited by sinking the island cell.

if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] == '0') return;Stop recursion on invalid or water cells.

dfs(grid, r + 1, c);Explore downward neighbor.

dfs(grid, r - 1, c);Explore upward neighbor.

dfs(grid, r, c + 1);Explore right neighbor.

dfs(grid, r, c - 1);Explore left neighbor.

count++;Increment island count after DFS completes.

var numIslands = function(grid) {
    if (!grid || grid.length === 0) return 0;
    const rows = grid.length, cols = grid[0].length;

    function dfs(r, c) {
        if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] === '0') return;
        grid[r][c] = '0'; // mark visited by sinking
        dfs(r + 1, c);
        dfs(r - 1, c);
        dfs(r, c + 1);
        dfs(r, c - 1);
    }

    let count = 0;
    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (grid[r][c] === '1') {
                dfs(r, c);
                count++;
            }
        }
    }
    return count;
};

// Test
const grid = [
    ['1','1','0','0','0'],
    ['1','1','0','0','0'],
    ['0','0','1','0','0'],
    ['0','0','0','1','1']
];
console.log(numIslands(grid)); // Expected output: 3

Line Notes

if (!grid || grid.length === 0) return 0;Guard clause for empty input.

function dfs(r, c) {Recursive DFS to explore and mark connected lands.

if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] === '0') return;Stop recursion on invalid or water cells.

grid[r][c] = '0';Mark current land cell visited by sinking it.

dfs(r + 1, c);Explore downward neighbor.

dfs(r - 1, c);Explore upward neighbor.

dfs(r, c + 1);Explore right neighbor.

dfs(r, c - 1);Explore left neighbor.

if (grid[r][c] === '1') {Start DFS on unvisited land cells.

count++;Increment island count after DFS completes.

⏱

Complexity

TimeO(m*n)

SpaceO(m*n) recursion stack in worst case

We visit each cell once, marking visited by modifying the grid. The recursion stack can be as large as the island size.

💡 This approach saves extra space for visited tracking but uses recursion stack which can be large for big islands.

Interview Verdict: Accepted

This is a common interview optimization that reduces space usage by modifying input, but be cautious if input modification is not allowed.

📊

All Approaches - One-Glance Tradeoffs

💡 In most interviews, the brute force DFS or BFS approach is sufficient and safe to implement. In-place DFS is a good optimization if input modification is allowed and space is constrained.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force DFS with Visited Set	O(m*n)	O(m*n) for visited set and recursion stack	Yes (deep recursion possible)	N/A	Good baseline; safe to code and explain
2. BFS with Queue	O(m*n)	O(m*n) for visited set and queue	No (iterative)	N/A	Good alternative to avoid recursion stack issues
3. In-place DFS (Modify Grid)	O(m*n)	O(m*n) recursion stack, no extra visited space	Yes	N/A	Mention as optimization if input modification allowed

💼

Interview Strategy

💡 Use this guide to understand the problem deeply and practice all approaches. Start with brute force to build intuition, then learn BFS and in-place optimizations. Practice coding and explaining each approach clearly.

How to Present

Clarify the problem and constraints with the interviewer.Explain the brute force DFS approach to find connected components.Discuss BFS as an alternative iterative approach.Mention in-place DFS to optimize space if allowed.Write clean, tested code and analyze complexity.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of graph traversal, handling of grid boundaries, marking visited nodes, and ability to optimize space/time. Clear communication and testing edge cases are critical.

Common Follow-ups

• What if diagonal connections count as adjacent? → Modify neighbor checks to include diagonals.
• Can you solve it without extra space? → Use in-place DFS to mark visited.
• How to handle very large grids? → BFS to avoid stack overflow or iterative DFS.
• What if the grid is mutable or immutable? → Choose approach accordingly.

💡 These follow-ups test your flexibility and understanding of problem variations and constraints.

🔍

Pattern Recognition

When to Use

1) Grid or matrix input with '1'/'0' or similar markers; 2) Need to find connected components or clusters; 3) Adjacency defined by neighbors (up/down/left/right); 4) Counting or labeling distinct groups.

Signature Phrases

count the number of islandsconnected horizontally or verticallygrid of '1's and '0's

NOT This Pattern When

Problems involving shortest path or weighted graphs are different patterns.

Similar Problems

Max Area of Island - find largest connected island sizeSurrounded Regions - capture surrounded regions using DFS/BFSNumber of Distinct Islands - count unique island shapes

Practice

1. Consider the following Python code for checking if a graph is a valid tree. What is the return value when calling valid_tree(4, [[0,1],[1,2],[2,3]])?

easy

A. true

B. false

C. Raises an exception

D. Returns null

Solution

1. Step 1: Check edge count

   Edges count is 3, nodes count is 4, so edges == n-1 condition passes.

2. Step 2: BFS traversal and cycle detection

   Starting from node 0, BFS visits nodes 0,1,2,3 without revisiting any node or detecting cycles. All nodes are visited.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Graph is connected and acyclic, so valid tree [OK]

Hint: Edges must be n-1 and BFS visits all nodes [OK]

Common Mistakes:

• Confusing cycle detection with revisiting parent
• Forgetting to check all nodes visited

2. Examine the following buggy cloneGraph implementation. Which line contains the subtle bug that can cause infinite recursion or stack overflow on cyclic graphs?

medium

A. Line 7: clone = Node(node.val)

B. Line 5: if not node:

C. Line 3: def __init__(self, val = 0, neighbors = null):

D. Line 8: clone.neighbors = [cloneGraph(nei) for nei in node.neighbors]

Solution

1. Step 1: Identify recursion without visited tracking

   The code recursively clones neighbors without tracking visited nodes, causing infinite recursion on cycles.

2. Step 2: Locate the problematic line

   Line 8 recursively calls cloneGraph on neighbors without memoization, leading to repeated visits and stack overflow.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Missing visited map causes infinite recursion at line 8 [OK]

Hint: Recursive calls without visited tracking cause infinite loops [OK]

Common Mistakes:

• Thinking bug is in node creation line
• Assuming base case is missing

3. Examine the following buggy code for the Keys and Rooms problem:

def canVisitAllRooms(rooms):
    n = len(rooms)
    visited = [false] * n
    count = 0
    def dfs(room):
        if visited[room]:
            return
        for key in rooms[room]:
            dfs(key)
        visited[room] = true
        nonlocal count
        count += 1
    dfs(0)
    return count == n

What is the bug in this code?

medium

A. Visited marking happens after recursive calls, causing repeated visits

B. Count is incremented before marking visited, causing off-by-one errors

C. Visited array is initialized incorrectly with zeros instead of false

D. DFS is called on room 0 instead of all rooms

Solution

1. Step 1: Analyze visited marking position

   Visited is marked after recursive calls, so the same room can be visited multiple times during recursion.

2. Step 2: Identify consequence of bug

   This causes repeated visits and potentially infinite recursion or incorrect count.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Visited must be marked before recursion to avoid revisits [OK]

Hint: Mark visited before recursion to prevent repeated visits [OK]

Common Mistakes:

• Marking visited after recursion leads to infinite loops
• Incrementing count before visited marking
• Incorrect initialization of visited array

4. What is the time complexity of the BFS-based algorithm to find the maximum area of an island in an m x n grid, where each cell is visited at most once?

medium

A. O((m * n)^2) -- BFS could revisit cells multiple times in worst case

B. O(m + n) -- because BFS visits each row and column once

C. O(m * n) -- each cell is visited once and neighbors checked constant times

D. O(m * n) plus extra O(m * n) space for the visited set

Solution

1. Step 1: Identify BFS visits each cell at most once

   Each cell is enqueued and dequeued once, so total operations proportional to number of cells.

2. Step 2: Each cell checks up to 4 neighbors in constant time

   Neighbor checks are constant per cell, so total is O(m*n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Linear in grid size, no repeated visits [OK]

Hint: Each cell visited once -> O(m*n) time [OK]

Common Mistakes:

• Assuming BFS revisits cells multiple times
• Confusing rows+cols with total cells
• Ignoring constant neighbor checks

5. Suppose the graph edges can have negative weights but no negative cycles. Which algorithm modification or choice correctly computes the shortest network delay times from a start node?

hard

A. Use DFS with path relaxation and memoization to handle negative weights efficiently.

B. Use Dijkstra's algorithm with a priority queue as usual; it handles negative weights correctly.

C. Use BFS since negative weights can be ignored for shortest paths.

D. Use Bellman-Ford algorithm to relax edges repeatedly, detecting negative cycles if any.

Solution

1. Step 1: Recognize that Dijkstra's algorithm fails with negative weights because it assumes non-negative edge costs

   BFS cannot handle weighted edges properly, and DFS with memoization is inefficient and may not terminate correctly.

2. Step 2: Bellman-Ford algorithm is designed to handle negative weights and detect negative cycles by repeated edge relaxation

   It guarantees correct shortest paths if no negative cycles exist.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Bellman-Ford handles negative weights safely [OK]

Hint: Bellman-Ford handles negative weights; Dijkstra does not [OK]

Common Mistakes:

• Using Dijkstra with negative weights incorrectly
• Assuming BFS works for weighted graphs
• Believing DFS with memoization is efficient here