5 Best Ways to Count Number of Islands in a Given Matrix in Python

Rate this post
Counting Number of Islands in a Matrix Using Python

πŸ’‘ Problem Formulation: The challenge involves writing a program to count the number of ‘islands’ in a 2D matrix, where an island is formed by adjacent (‘up’, ‘down’, ‘left’, ‘right’) 1s and surrounded by 0s. For example, the input matrix may look like [[1,1,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]], where this particular input would yield an output of 3 islands.

Method 1: Depth First Search (DFS)

Depth First Search (DFS) is a classical graph traversal algorithm that can be used to explore and mark each part of an island. The basic approach is to iterate over each cell in the matrix, and every time a ‘1’ (land) is found, increment the island count and use DFS to mark all adjacent land as visited.

Here’s an example:

def dfs(matrix, i, j):
    if i < 0 or j < 0 or i >= len(matrix) or j >= len(matrix[0]) or matrix[i][j] == 0:
        return
    matrix[i][j] = 0
    dfs(matrix, i+1, j)
    dfs(matrix, i-1, j)
    dfs(matrix, i, j+1)
    dfs(matrix, i, j-1)

def numIslands(matrix):
    count = 0
    for i in range(len(matrix)):
       for j in range(len(matrix[0])):
           if matrix[i][j] == 1:
               dfs(matrix, i, j)
               count += 1
    return count

grid = [[1,1,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]]
print(numIslands(grid))

Output:

3

This code defines a dfs function that traverses the matrix, marking visited land (1s) by sinking (changing them to 0s), preventing double-counting. The numIslands function then counts the islands using dfs when it finds unvisited land.

Method 2: Breadth First Search (BFS)

Breadth First Search (BFS) involves using a queue to explore levels of adjacent nodes (cells with ‘1’s) iteratively. As with DFS, once a ‘1’ is found, an island counter is incremented and BFS is used to explore and mark all reachable cells.

Here’s an example:

from collections import deque

def bfs(matrix, start):
    queue = deque([start])
    matrix[start[0]][start[1]] = 0
    directions = [(1,0), (-1,0), (0,1), (0,-1)]
    while queue:
        i, j = queue.popleft()
        for direction in directions:
            new_i, new_j = i + direction[0], j + direction[1]
            if 0 <= new_i < len(matrix) and 0 <= new_j < len(matrix[0]) and matrix[new_i][new_j] == 1:
                queue.append((new_i, new_j))
                matrix[new_i][new_j] = 0

def numIslands(matrix):
    count = 0
    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            if matrix[i][j] == 1:
                bfs(matrix, (i, j))
                count += 1
    return count

grid = [[1,1,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]]
print(numIslands(grid))

Output:

3

The bfs function uses a queue to visit and mark cells, ensuring each found ‘1’ leads to a complete exploration of the corresponding island. The numIslands function uses this to count the islands in the matrix.

Method 3: Union Find

The Union Find algorithm provides another way to solve this problem by grouping adjacent lands (1s) into a single connected component (island). Each land cell’s index gets mapped to a parent, and these parents are unified for adjacent lands.

Here’s an example:

class UnionFind:
    def __init__(self, grid):
        m, n = len(grid), len(grid[0])
        self.parent = [-1] * (m * n)
        self.count = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    self.parent[i * n + j] = i * n + j
                    self.count += 1
        self.rank = [0] * (m * n)

    def find(self, i):
        if self.parent[i] != i:
            self.parent[i] = self.find(self.parent[i])
        return self.parent[i]

    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 or not grid[0]:
        return 0

    uf = UnionFind(grid)
    directions = [(1,0), (-1,0), (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:
                for direction in directions:
                    ni, nj = i + direction[0], j + direction[1]
                    if ni >= 0 and ni < m and nj >= 0 and nj < n and grid[ni][nj] == 1:
                        uf.union(i * n + j, ni * n + nj)
    return uf.count

grid = [[1,1,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]]
print(numIslands(grid))

Output:

3

The UnionFind class initialises with each land cell as its own island. The find function locates the root parent, and the union function merges islands. The numIslands function then applies Union Find to our grid to yield the island count.

Method 4: Recursive Backtracking

Recursive backtracking is similar in concept to DFS but utilizes recursion in a more explicit and patterned manner. It systematically explores all of the possibilities of the island formations by backtracking as soon as it realizes it has ventured into water (0) or out of bounds.

Here’s an example:

def explore_island(matrix, i, j):
    if i < 0 or j < 0 or i >= len(matrix) or j >= len(matrix[0]) or matrix[i][j] == 0:
        return
    matrix[i][j] = 0
    explore_island(matrix, i+1, j)
    explore_island(matrix, i-1, j)
    explore_island(matrix, i, j+1)
    explore_island(matrix, i, j-1)

def numIslands(matrix):
    count = 0
    for i in range(len(matrix)):
       for j in range(len(matrix[0])):
           if matrix[i][j] == 1:
               explore_island(matrix, i, j)
               count += 1
    return count

grid = [[1,1,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]]
print(numIslands(grid))

Output:

3

Here, the explore_island function aims to visit every part of an island and then “backtrack”, effectively marking the area by sinking the land. The numIslands function uses these explorations to count total islands.

Bonus One-Liner Method 5: List Comprehension with DFS

A Pythonic one-liner approach, though less readable, can also count islands using list comprehension and embedded DFS calls for each unvisited land cell.

Here’s an example:

numIslands = lambda grid: sum(dfs(grid, i, j) or 0 for i in range(len(grid)) for j in range(len(grid[0])) if grid[i][j])

def dfs(grid, i, j):
    if 0 <= i < len(grid) and 0 <= j < len(grid[0]) and grid[i][j]:
        grid[i][j] = 0
        list(map(dfs, [grid]*4, [i+1, i-1, i, i], [j, j, j+1, j-1]))
        return 1

grid = [[1,1,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]]
print(numIslands(grid))

Output:

3

This one-liner leverages a lambda function wrapping around a summation of DFS calls. The dfs function is called for every ‘1’ detected in the grid, leading to an island count.

Summary/Discussion

  • Method 1: Depth First Search (DFS). The classic approach for exploring connected components. Strengths: Simple implementation. Weaknesses: Recursive stack space can be a concern for large matrices.
  • Method 2: Breadth First Search (BFS). Iterative approach using queues. Strengths: Can handle larger matrices better than DFS due to iterative nature. Weaknesses: Generally requires more memory due to queue.
  • Method 3: Union Find. Efficient for large datasets, especially when the number of union and find operations are numerous. Strengths: Very efficient in practice with path compression. Weaknesses: More complex implementation.
  • Method 4: Recursive Backtracking. Intuitive pattern-based recursion that systematically explores the searching space. Strengths: Conceptually simple and elegant. Weaknesses: Recursive stack space, identical to DFS concerns.
  • Bonus Method 5: List Comprehension with DFS. A concise Pythonic approach that uses advanced features of the language. Strengths: Very short code. Weaknesses: Can be difficult to read and understand, especially for new developers.