Teaching Kids Programming – Transform Matrix to One Connected Component using Breadth 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?

Last lesson, we talk about using the Depth First Search (Recursion) to traverse the connected pixels (island) in a color map. We can do this via Breadth First Search Algorithm.

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

We just replace the previous DFS with the BFS and the algorithm should continue to work. We iterate over each pixel – and if it is not marked as visited (-1), we perform a Breadth First Search Algorithm to mark the connected pixels visited.

And then we count each color to see how many islands (connected pixels). The one with the most are kept.

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 bfs(r, c, x):
            q = deque([(r, c)])
            while q:
                rr, cc = q.popleft()                
                for dr, dc in ((1, 0), (0, 1), (-1, 0), (0, -1)):
                    nr = dr + rr
                    nc = dc + cc
                    if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] == x:
                        matrix[nr][nc] = -1
                        q.append((nr, nc))                
        for r in range(rows):
            for c in range(cols):
                if matrix[r][c] != -1:
                    color = matrix[r][c]
                    bfs(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 bfs(r, c, x):
            q = deque([(r, c)])
            while q:
                rr, cc = q.popleft()                
                for dr, dc in ((1, 0), (0, 1), (-1, 0), (0, -1)):
                    nr = dr + rr
                    nc = dc + cc
                    if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] == x:
                        matrix[nr][nc] = -1
                        q.append((nr, nc))                
        for r in range(rows):
            for c in range(cols):
                if matrix[r][c] != -1:
                    color = matrix[r][c]
                    bfs(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. And the space complexity is O(N) as we are using a deque (double ended queue) to perform the BFS.

–EOF (The Ultimate Computing & Technology Blog) —