Teaching Kids Programming – Depth First Search Algorithm to Count the Number of Islands

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a two-dimensional integer matrix of 1s and 0s, return the number of “islands” in the matrix. A 1 represents land and 0 represents water, so an island is a group of 1s that are neighboring whose perimeter is surrounded by water.

Note: Neighbors can only be directly horizontal or vertical, not diagonal.

Constraints
n, m ≤ 100 where n and m are the number of rows and columns in matrix.

Example 1
Input

1 2 3 4

matrix = [     [1, 1],     [1, 0] ]

matrix = [
    [1, 1],
    [1, 0]
]

Output
1

Example 2
Input

1 2 3 4 5 6 7 8

matrix = [     [1, 0, 0, 0, 0],     [0, 0, 1, 1, 0],     [0, 1, 1, 0, 0],     [0, 0, 0, 0, 0],     [1, 1, 0, 0, 1],     [1, 1, 0, 0, 1] ]

matrix = [
    [1, 0, 0, 0, 0],
    [0, 0, 1, 1, 0],
    [0, 1, 1, 0, 0],
    [0, 0, 0, 0, 0],
    [1, 1, 0, 0, 1],
    [1, 1, 0, 0, 1]
]

Output
4

Example 3
Input

1 2 3 4

matrix = [     [0, 1],     [1, 0] ]

matrix = [
    [0, 1],
    [1, 0]
]

Output
2

Count the Number of Island by Depth First Search Algorithm

At each pixel, we can start a Depth First Search that recursively mark all connected 1’s zeros and return 1. Then by iterating over all pixels, we get the number of island (connected pieces). We mark lands zeros so that we don’t recursively visit them again.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def numberOfLands(self, matrix):
        rows, cols = len(matrix), len(matrix[0])
        def dfs(r, c):
            if r < 0 or c < 0 or r == rows or c == cols:
                return 0
            if matrix[r][c] == 0:
                return 0
            matrix[r][c] = 0
            dfs(r - 1, c)
            dfs(r + 1, c)
            dfs(r, c - 1)
            dfs(r, c + 1)
            return 1
        ans = 0
        for r in range(rows):
            for c in range(cols):
                ans += dfs(r, c)
        return ans

class Solution:
    def numberOfLands(self, matrix):
        rows, cols = len(matrix), len(matrix[0])
        def dfs(r, c):
            if r < 0 or c < 0 or r == rows or c == cols:
                return 0
            if matrix[r][c] == 0:
                return 0
            matrix[r][c] = 0
            dfs(r - 1, c)
            dfs(r + 1, c)
            dfs(r, c - 1)
            dfs(r, c + 1)
            return 1
        ans = 0
        for r in range(rows):
            for c in range(cols):
                ans += dfs(r, c)
        return ans

The time complexity is O(N) as each pixel will be visited once (we mark visited pixels zeros). With the Same DFS algorithm, we can find the largest land size as well: Teaching Kids Programming – Depth First Search Algorithm to Find the Largest Land

Island Problems and Algorithms:

• Teaching Kids Programming – Island Shape Perimeter Algorithm
• Teaching Kids Programming – Depth First Search Algorithm to Count the Number of Islands
• Teaching Kids Programming – Depth First Search Algorithm to Find the Largest Land
• Teaching Kids Programming – Recursive Depth First Search Algorithm to Count the Surrounded Islands

–EOF (The Ultimate Computing & Technology Blog) —