How to Solve: Number of Islands (BFS/DFS/Union Find) – Complete Guide for FAANG Interviews

How to Solve: Number of Islands (BFS/DFS/Union Find) – Complete Guide for FAANG Interviews

? Introduction

"This problem appears in 1 out of every 3 onsite interviews—mastering it proves you can handle graph traversal, connected components, and trade-offs between BFS, DFS, and Union-Find—skills that separate L4 from L5 engineers."

? WHAT YOU NEED TO KNOW FIRST

Before tackling Number of Islands, ensure you understand: 1. Graph Traversal (BFS/DFS) – How to explore nodes in a grid or graph. 2. Union-Find (Disjoint Set Union, DSU) – A data structure for tracking connected components efficiently. 3. Visited Tracking – How to mark nodes as visited to avoid cycles and redundant work.

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK

Repeat this checklist for every "Number of Islands" problem:

1. Clarify the Problem
2. Is the grid static (DFS/BFS) or dynamic (Union-Find)?
3. Are diagonals considered connected? (Default: No, unless specified.)

4. Can the grid be modified? (If yes, in-place modification is allowed.)

5. Choose the Right Approach

6. DFS/BFS: Best for static grids (one-time traversal).

7. Union-Find: Best for dynamic grids (cells can change, e.g., "What if water turns into land?").

8. Initialize Data Structures

9. DFS/BFS: visited matrix (or modify grid in-place).

10. Union-Find: parent and rank arrays (or dictionaries for sparse grids).

11. Traverse the Grid

12. For each cell:

    • If it’s 1 (land) and unvisited, increment island count.
    • Explore all connected 1s (DFS/BFS) or union them (Union-Find).

13. Handle Edge Cases

14. Empty grid → Return 0.
15. Single-cell grid → Return 1 if 1, else 0.

16. All 0s → Return 0.

17. Optimize for Time/Space

18. DFS/BFS: Time = O(M×N), Space = O(M×N) (worst-case stack/queue).

19. Union-Find: Time = O(M×N × α(M×N)) (near-linear due to path compression), Space = O(M×N).

20. Test with Examples

21. Run through 2-3 test cases (small, large, edge cases).

? WORKED EXAMPLES

Example 1 – Basic (DFS)

Problem: Given a 2D grid of '1' (land) and '0' (water), count the number of islands (connected 1s horizontally/vertically).

Solution (DFS - Recursive):

def numIslands(grid):

    if not grid:

        return 0


    rows, cols = len(grid), len(grid[0])

    count = 0


    def dfs(i, j):

        if i < 0 or j < 0 or i >= rows or j >= cols or grid[i][j] != '1':

            return

        grid[i][j] = '0'  # Mark as visited (in-place)

        dfs(i + 1, j)

        dfs(i - 1, j)

        dfs(i, j + 1)

        dfs(i, j - 1)


    for i in range(rows):

        for j in range(cols):

            if grid[i][j] == '1':

                count += 1

                dfs(i, j)

    return count

Time Complexity: O(M×N) (each cell visited once). Space Complexity: O(M×N) (worst-case recursion stack).

Why This Works: - DFS explores all connected 1s, marking them as 0 to avoid revisiting. - Each 1 triggers a new island count.

Example 2 – Medium (BFS)

Problem: Same as above, but avoid recursion (e.g., large grid).

Solution (BFS - Queue):

from collections import deque

def numIslands(grid):

    if not grid:

        return 0


    rows, cols = len(grid), len(grid[0])

    count = 0


    for i in range(rows):

        for j in range(cols):

            if grid[i][j] == '1':

                count += 1

                queue = deque([(i, j)])

                grid[i][j] = '0'  # Mark as visited


                while queue:

                    x, y = queue.popleft()

                    for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]:

                        nx, ny = x + dx, y + dy

                        if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == '1':

                            grid[nx][ny] = '0'

                            queue.append((nx, ny))

    return count

Time Complexity: O(M×N). Space Complexity: O(min(M, N)) (queue size in worst case).

Why This Works: - BFS avoids recursion stack overflow by using a queue. - Still marks cells as visited in-place.

Example 3 – Hard (Union-Find)

Problem: Same grid, but cells can change dynamically (e.g., "What if water turns into land?").

Solution (Union-Find):

class UnionFind:

    def __init__(self, grid):

        rows, cols = len(grid), len(grid[0])

        self.parent = {}

        self.rank = {}

        self.count = 0


        for i in range(rows):

            for j in range(cols):

                if grid[i][j] == '1':

                    self.parent[(i, j)] = (i, j)

                    self.rank[(i, j)] = 0

                    self.count += 1


    def find(self, x):

        if self.parent[x] != x:

            self.parent[x] = self.find(self.parent[x])  # Path compression

        return self.parent[x]


    def union(self, x, y):

        rootX = self.find(x)

        rootY = self.find(y)

        if rootX != rootY:

            if self.rank[rootX] > self.rank[rootY]:

                self.parent[rootY] = rootX

            elif self.rank[rootX] < self.rank[rootY]:

                self.parent[rootX] = rootY

            else:

                self.parent[rootY] = rootX

                self.rank[rootX] += 1

            self.count -= 1

def numIslands(grid):

    if not grid:

        return 0


    rows, cols = len(grid), len(grid[0])

    uf = UnionFind(grid)


    for i in range(rows):

        for j in range(cols):

            if grid[i][j] == '1':

                for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]:

                    ni, nj = i + dx, j + dy

                    if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == '1':

                        uf.union((i, j), (ni, nj))

    return uf.count

Time Complexity: O(M×N × α(M×N)) (near-linear due to path compression). Space Complexity: O(M×N) (for parent and rank dictionaries).

Why This Works: - Union-Find dynamically tracks connected components. - Path compression and union by rank keep operations nearly constant time.

❌ Common Mistakes

?️ INTERVIEW TrapS

? 1-Minute Recap (Closing Script)

"Alright, let’s lock this in. For Number of Islands: 1. Clarify: Is the grid static or dynamic? Are diagonals connected? 2. Choose: DFS/BFS for static grids, Union-Find for dynamic. 3. Traverse: For each 1, explore all connected 1s (DFS/BFS) or union them (Union-Find). 4. Optimize: Use in-place modification to save space, path compression for Union-Find. 5. Test: Run through small, large, and edge cases.

DFS/BFS is simpler, but Union-Find shines when the grid changes. Memorize the direction arrays, and you’re golden. Now go crush that interview!

? Final Notes

• Practice Variations:
• "Max Area of Island" (DFS/BFS with area tracking).
• "Number of Closed Islands" (DFS/BFS with boundary checks).
• "Surrounded Regions" (DFS/BFS from borders).
• Whiteboard Tip: Draw a small grid (3x3) and walk through DFS/BFS step-by-step.

This framework is directly usable in any FAANG interview. Good luck! ?