Teaching Kids Programming – Transform Matrix to One Connected Component using Recursive Depth First Search Algorithm

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given a two-dimensional list of integers matrix. Each cell’s value represents its color and adjacent cells (top, bottom, left, right) with the same color are considered to be in the same group. Consider an operation where we set all cells in one group to some color. Return the minimum number of operations required so that every cell has the same color. Once the color is transformed, it cannot be set again.

Constraints
n, m ≤ 250 where n and m are the number of rows and columns in matrix
Example 1
Input

1 2 3 4 5

matrix = [     [1, 1, 1, 1],     [2, 2, 2, 2],     [1, 3, 1, 2] ]

matrix = [
    [1, 1, 1, 1],
    [2, 2, 2, 2],
    [1, 3, 1, 2]
]

Output
2
Explanation
We can fill the group with 2 as color into 1 and then fill 3 with 1. The key phrase here is “once a color is transformed, it cannot be set again.”

Hints:
Think greedy — which color should we transform all of the other colors into?

Transform Matrix to One Connected Component (Color) using Recursive Depth First Search Algorithm

Let’s count the number of islands for each color/number. Then the optimal solution is to keep the color/integer with the most connected pieces.

We can use either Depth First Search or Breadth First Search Algorithm to count the number of island. To avoid the pixel being visited twice, we can use a hash map or hash set to remember the pixels, or simply we can set visited pixel to minus one.

Then, the answer would be the total number of islands (connected pieces, colors) minus the number of the most islands.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution:
    def solve(self, matrix):
        if not matrix:
            return 0
        rows = len(matrix)
        data = defaultdict(int)
        cols = len(matrix[0])
        def dfs(r, c, x):
            if r < 0 or c < 0 or r >= rows or c >= cols:
                return
            if matrix[r][c] != x:
                return 
            matrix[r][c] = -1
            dfs(r - 1, c, x)
            dfs(r + 1, c, x)
            dfs(r, c - 1, x)
            dfs(r, c + 1, x)            
        for r in range(rows):
            for c in range(cols):
                if matrix[r][c] != -1:
                    color = matrix[r][c]
                    dfs(r, c, color)
                    data[color] += 1
        return sum(data.values()) - max(data.values())   

class Solution:
    def solve(self, matrix):
        if not matrix:
            return 0
        rows = len(matrix)
        data = defaultdict(int)
        cols = len(matrix[0])
        def dfs(r, c, x):
            if r < 0 or c < 0 or r >= rows or c >= cols:
                return
            if matrix[r][c] != x:
                return 
            matrix[r][c] = -1
            dfs(r - 1, c, x)
            dfs(r + 1, c, x)
            dfs(r, c - 1, x)
            dfs(r, c + 1, x)            
        for r in range(rows):
            for c in range(cols):
                if matrix[r][c] != -1:
                    color = matrix[r][c]
                    dfs(r, c, color)
                    data[color] += 1
        return sum(data.values()) - max(data.values())   

Time complexity is O(N) where N is the number of pixels in the map. The space complexity is O(N) where we need to use a dictionary to store the counter for each color.

We can do BFS as well: Teaching Kids Programming – Transform Matrix to One Connected Component using Breadth First Search Algorithm

–EOF (The Ultimate Computing & Technology Blog) —