#200

Medium

auto_awesomeArray plus Depth-First Search

LeetCode Problem Workspace

Number of Islands

Count the number of distinct islands in a binary grid using array traversal combined with depth-first search exploration techniques.

array depth first search breadth first search union find matrix

Problem Statement

Given an m x n 2D grid representing a map of '1's (land) and '0's (water), determine the total number of separate islands. An island consists of horizontally or vertically adjacent '1's and is entirely surrounded by water.

Each cell can only belong to one island. You must process the grid efficiently, applying depth-first search, breadth-first search, or union-find strategies to identify all islands without revisiting previously counted land cells. Examples illustrate typical island configurations.

Examples

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 details omitted.

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

Example details omitted.

Constraints

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] is '0' or '1'.

Solution Approach

Depth-First Search (DFS) Traversal

Iterate over each cell in the grid. When a '1' is found, initiate a DFS to mark all connected lands as visited. Each DFS call counts as a single island. This approach leverages recursion or an explicit stack to traverse neighbors efficiently.

Breadth-First Search (BFS) Traversal

For each unvisited land cell, use a queue to explore all neighboring land cells level by level. Mark cells as visited to prevent double-counting. BFS ensures systematic traversal and can handle larger grids iteratively without deep recursion stack issues.

Union-Find Approach

Represent each land cell as a node in a disjoint set. Merge connected land nodes using union operations. After processing the grid, the number of unique sets corresponds to the total islands. This method is effective for dynamic connectivity but requires careful initialization.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity varies: DFS/BFS is O(m n) as each cell is visited once. Union-Find is O(m n * α(m n)) where α is the inverse Ackermann function. Space complexity is O(m n) for visited markers or recursion/queue storage depending on the approach.

What Interviewers Usually Probe

Expect array traversal plus DFS/BFS as a primary approach.
Check if candidate handles edge cases like all water or single-cell islands.
Look for marking strategies to prevent revisiting cells and miscounting islands.

Common Pitfalls or Variants

Common pitfalls

Failing to mark visited cells, causing infinite loops or double-counting.
Confusing diagonal adjacency with vertical/horizontal adjacency.
Using recursion without stack limits, which may cause stack overflow on large grids.

Follow-up variants

Count islands considering diagonal adjacency as connected.
Return the size of the largest island instead of the count.
Allow dynamic addition of land cells and update the island count incrementally.

FAQ

What is the best approach to solve Number of Islands?

DFS or BFS is typically optimal; DFS is simple recursively, BFS uses a queue to avoid deep recursion issues.

Can diagonal cells count as connected islands?

By default, only horizontal and vertical connections count; diagonal connections create a different variant of the problem.

How do I prevent revisiting cells during DFS/BFS?

Mark each visited land cell by changing its value or using a separate visited matrix to avoid double-counting islands.

What is the time complexity for Number of Islands?

DFS and BFS both run in O(m*n) time, visiting each cell exactly once; Union-Find has slightly higher overhead.

Does GhostInterview handle large grids efficiently?

Yes, it guides the implementation to manage visited markers and traversal order to prevent stack overflow or excessive memory usage.

terminal

Solution

Solution 1: DFS

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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        def dfs(i, j):
            grid[i][j] = '0'
            for a, b in pairwise(dirs):
                x, y = i + a, j + b
                if 0 <= x < m and 0 <= y < n and grid[x][y] == '1':
                    dfs(x, y)

        ans = 0
        dirs = (-1, 0, 1, 0, -1)
        m, n = len(grid), len(grid[0])
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    dfs(i, j)
                    ans += 1
        return ans

Solution 2: BFS

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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        def dfs(i, j):
            grid[i][j] = '0'
            for a, b in pairwise(dirs):
                x, y = i + a, j + b
                if 0 <= x < m and 0 <= y < n and grid[x][y] == '1':
                    dfs(x, y)

        ans = 0
        dirs = (-1, 0, 1, 0, -1)
        m, n = len(grid), len(grid[0])
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    dfs(i, j)
                    ans += 1
        return ans

Solution 3: Union-Find

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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        def dfs(i, j):
            grid[i][j] = '0'
            for a, b in pairwise(dirs):
                x, y = i + a, j + b
                if 0 <= x < m and 0 <= y < n and grid[x][y] == '1':
                    dfs(x, y)

        ans = 0
        dirs = (-1, 0, 1, 0, -1)
        m, n = len(grid), len(grid[0])
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    dfs(i, j)
                    ans += 1
        return ans

Continue Practicing

#130 surrounded regions #695 max area of island #778 swim in rising water