Home
Find Maximum Connected Colors (Values) in a 2D Grid using DFS or BFS Algorithm
Tags:, , , ,

Find Maximum Connected Colors (Values) in a 2D Grid using DFS or BFS Algorithm

November 18, 2019 No Comments algorithms, BFS, DFS, python, recursive

Given a 2D Grid with integer values representing the colours, you are asked (in an interview probably) to find out the maximum connected colour sizes. A colour is connected to another if it is horizontally or vertically connecting to another piece in the Grid that has the same value. For example, given the following 2D Grid:

1
2
3
4
5

grid = [[1, 0, 1, 1],
        [0, 1, 1, 0],
        [1, 0, 1, 1],
        [1, 0, 1, 1]
]
grid = [[1, 0, 1, 1],
        [0, 1, 1, 0],
        [1, 0, 1, 1],
        [1, 0, 1, 1]
]

The maximum connected colours are the the following (leaving out others) which has size of 8:

1
2
3
4
5

grid = [[0, 0, 1, 1],
        [0, 1, 1, 0],
        [0, 0, 1, 1],
        [0, 0, 1, 1]
]
grid = [[0, 0, 1, 1],
        [0, 1, 1, 0],
        [0, 0, 1, 1],
        [0, 0, 1, 1]
]

Let’s define the grid in Python:

1
2
3

class Grid:
    def __init__(self, data):
        self.data = data
class Grid:
    def __init__(self, data):
        self.data = data

And a few helper function return the colour for a pixel and -1 if the coordinate is invalid.

1
2
3
4
5

def data_at(self, row, col):
    if row >= 0 and row < len(self.data) and \
        col >= 0 and col < len(self.data[row]):
        return self.data[row][col]
    return -1
def data_at(self, row, col):
    if row >= 0 and row < len(self.data) and \
        col >= 0 and col < len(self.data[row]):
        return self.data[row][col]
    return -1

With this, then we can return neighbours which should have valid coordinates and same colour:

1
2
3
4
5
6
7

def neighbours(self, row, col):
    P = [[0, -1], [0, 1], [1, 0], [-1, 0]]
    n = []
    for p in P:
        if self.data[row][col] == self.data_at(row + p[0], col + p[1]):
            n.append((row + p[0], col + p[1]))
    return n
def neighbours(self, row, col):
    P = [[0, -1], [0, 1], [1, 0], [-1, 0]]
    n = []
    for p in P:
        if self.data[row][col] == self.data_at(row + p[0], col + p[1]):
            n.append((row + p[0], col + p[1]))
    return n

We are using the coordinate offsets here to save a few typings.

Finding Connected Colours using Depth First Search Algorithm

The Depth First Search Algorithm should be conducted for each pixel, thus in the double for loop:

1
2
3

for row in range(len(self.data)):
    for col in range(len(self.data[row])):                
       ans = max(ans, self.dfs(row, col, {}))
for row in range(len(self.data)):
    for col in range(len(self.data[row])):                
       ans = max(ans, self.dfs(row, col, {}))

The Depth First Search function takes the first two as coordinate parameters, and the third parameter is a dictionary (hash set) which is used to mark the visited pixel – to avoid re-visiting the same pixels over and over again – otherwise the DFS will be endless.

1
2
3
4
5
6
7
8
9

def dfs(self, row, col, visited):
    key = str(row) + "," + str(col)
    if key in visited:
        return 0
    visited[key] = True
    ans = 1
    for n in self.neighbours(row, col):
        ans += self.dfs(n[0], n[1], visited)
    return ans
def dfs(self, row, col, visited):
    key = str(row) + "," + str(col)
    if key in visited:
        return 0
    visited[key] = True
    ans = 1
    for n in self.neighbours(row, col):
        ans += self.dfs(n[0], n[1], visited)
    return ans

The current position is checked first to ensure that it has never been handled. Then, we add the current pixel to the visited list. Then, for all its neighbours, we call the DFS and accumulate the result number.

The DFS can be implemented in an iterative fashion.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

def dfs_iterative(self, row, col):
    st = [(row, col)]
    visited = {}
    ans = 0
    while st:
        cur = st.pop()
        key = str(cur[0]) + "," + str(cur[1])            
        if key in visited:
            continue
        visited[key] = True
        ans += 1
        for n in self.neighbours(cur[0], cur[1]):                
            st.append((n[0], n[1]))
    return ans
def dfs_iterative(self, row, col):
    st = [(row, col)]
    visited = {}
    ans = 0
    while st:
        cur = st.pop()
        key = str(cur[0]) + "," + str(cur[1])            
        if key in visited:
            continue
        visited[key] = True
        ans += 1
        for n in self.neighbours(cur[0], cur[1]):                
            st.append((n[0], n[1]))
    return ans

The key to implement a recursion using iterative approach is using a stack (First In Last Out). After the validation of a new node (visited the first time), we increment the counter – as we find one more connected piece.

Finding Connected Colours using Breadth First Search Algorithm

The BFS is similar, except that the order of the neighbour nodes is different. This is achieved via using a queue data structure (First In First Out).

1
2
3
4
5
6
7
8
9
10
11
12
13
14

def bfs(self, row, col):
    q = [(row, col)]
    visited = {}
    ans = 0
    while len(q):
        cur = q.pop(0)
        key = str(cur[0]) + "," + str(cur[1])            
        if key in visited:
            continue
        visited[key] = True
        ans += 1
        for n in self.neighbours(cur[0], cur[1]):                
            q.append((n[0], n[1]))
    return ans        
def bfs(self, row, col):
    q = [(row, col)]
    visited = {}
    ans = 0
    while len(q):
        cur = q.pop(0)
        key = str(cur[0]) + "," + str(cur[1])            
        if key in visited:
            continue
        visited[key] = True
        ans += 1
        for n in self.neighbours(cur[0], cur[1]):                
            q.append((n[0], n[1]))
    return ans

Breadth First Search Algorithm is often implemented in a iterative approach and in this particular case, no difference (except the usage of stack or queue) to the iterative Depth First Search Algorithm i.e. you can count the number of pixels level by level (BFS) or as deep as possible (DFS).

Demo Code in Python

All above is included in the following Python code to demo the BFS or DFS:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

class Grid:
    def __init__(self, data):
        self.data = data
    
    def max_connected_grid(self, algorithm):
        ans = 1
        if algorithm == "DFS":
            for row in range(len(self.data)):
                for col in range(len(self.data[row])):                
                    ans = max(ans, self.dfs(row, col, {}))
        elif algorithm == 'DFS-I':
            for row in range(len(self.data)):
                for col in range(len(self.data[row])):                
                    ans = max(ans, self.dfs_iterative(row, col))
        elif algorithm == 'BFS':
            for row in range(len(self.data)):
                for col in range(len(self.data[row])):                
                    ans = max(ans, self.bfs(row, col))
        else:
            raise Exception('unknown algorithm ' + algorithm)
        return ans
 
    def neighbours(self, row, col):
        P = [[0, -1], [0, 1], [1, 0], [-1, 0]]
        n = []
        for p in P:
            if self.data[row][col] == self.data_at(row + p[0], col + p[1]):
                n.append((row + p[0], col + p[1]))
        return n
 
    def data_at(self, row, col):
        if row >= 0 and row < len(self.data) and \
            col >= 0 and col < len(self.data[row]):
            return self.data[row][col]
        # returning -1 to indicate invalid coordinates
        return -1
 
    def dfs_iterative(self, row, col):
        st = [(row, col)]
        visited = {}
        ans = 0
        while len(st):
            cur = st.pop()
            key = str(cur[0]) + "," + str(cur[1])            
            if key in visited:
                continue
            visited[key] = True
            ans += 1
            for n in self.neighbours(cur[0], cur[1]):                
                st.append((n[0], n[1]))
        return ans        
 
    def dfs(self, row, col, visited):
        key = str(row) + "," + str(col)
        if key in visited:
            return 0
        visited[key] = True
        ans = 1
        for n in self.neighbours(row, col):
            ans += self.dfs(n[0], n[1], visited)
        return ans
 
    def bfs(self, row, col):
        q = [(row, col)]
        visited = {}
        ans = 0
        while len(q):
            cur = q.pop(0) # deque the front element
            key = str(cur[0]) + "," + str(cur[1])            
            if key in visited:
                continue
            visited[key] = True
            ans += 1
            for n in self.neighbours(cur[0], cur[1]):                
                # push it to the end of the queue
                q.append((n[0], n[1]))
        return ans        
        
if __name__ == '__main__':
    grid = [[1, 0, 1, 1],
            [0, 1, 1, 0],
            [1, 0, 1, 1],
            [1, 0, 1, 1]
    ]
 
    G = Grid(grid)
    # all the below should print same answer - 8
    print(G.max_connected_grid("DFS"))
    print(G.max_connected_grid("DFS-I"))
    print(G.max_connected_grid("BFS"))
class Grid:
    def __init__(self, data):
        self.data = data
    
    def max_connected_grid(self, algorithm):
        ans = 1
        if algorithm == "DFS":
            for row in range(len(self.data)):
                for col in range(len(self.data[row])):                
                    ans = max(ans, self.dfs(row, col, {}))
        elif algorithm == 'DFS-I':
            for row in range(len(self.data)):
                for col in range(len(self.data[row])):                
                    ans = max(ans, self.dfs_iterative(row, col))
        elif algorithm == 'BFS':
            for row in range(len(self.data)):
                for col in range(len(self.data[row])):                
                    ans = max(ans, self.bfs(row, col))
        else:
            raise Exception('unknown algorithm ' + algorithm)
        return ans

    def neighbours(self, row, col):
        P = [[0, -1], [0, 1], [1, 0], [-1, 0]]
        n = []
        for p in P:
            if self.data[row][col] == self.data_at(row + p[0], col + p[1]):
                n.append((row + p[0], col + p[1]))
        return n

    def data_at(self, row, col):
        if row >= 0 and row < len(self.data) and \
            col >= 0 and col < len(self.data[row]):
            return self.data[row][col]
        # returning -1 to indicate invalid coordinates
        return -1

    def dfs_iterative(self, row, col):
        st = [(row, col)]
        visited = {}
        ans = 0
        while len(st):
            cur = st.pop()
            key = str(cur[0]) + "," + str(cur[1])            
            if key in visited:
                continue
            visited[key] = True
            ans += 1
            for n in self.neighbours(cur[0], cur[1]):                
                st.append((n[0], n[1]))
        return ans        

    def dfs(self, row, col, visited):
        key = str(row) + "," + str(col)
        if key in visited:
            return 0
        visited[key] = True
        ans = 1
        for n in self.neighbours(row, col):
            ans += self.dfs(n[0], n[1], visited)
        return ans

    def bfs(self, row, col):
        q = [(row, col)]
        visited = {}
        ans = 0
        while len(q):
            cur = q.pop(0) # deque the front element
            key = str(cur[0]) + "," + str(cur[1])            
            if key in visited:
                continue
            visited[key] = True
            ans += 1
            for n in self.neighbours(cur[0], cur[1]):                
                # push it to the end of the queue
                q.append((n[0], n[1]))
        return ans        
        
if __name__ == '__main__':
    grid = [[1, 0, 1, 1],
            [0, 1, 1, 0],
            [1, 0, 1, 1],
            [1, 0, 1, 1]
    ]

    G = Grid(grid)
    # all the below should print same answer - 8
    print(G.max_connected_grid("DFS"))
    print(G.max_connected_grid("DFS-I"))
    print(G.max_connected_grid("BFS"))

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
1077 words
Last Post: Algorithms to Shift a 2D Grid/Matrix In-Place
Next Post: VBScript Function to Convert an Integer to Binary String Representation

The Permanent URL is: Find Maximum Connected Colors (Values) in a 2D Grid using DFS or BFS Algorithm

Related posts:

  1. Planning To Update Your Website For 2020? Read This. Looking to update your website for 2020? If so, it’s important to be aware of...
  2. C++ Chess Board Printing in Windows Using CodePage 437 – Extended ASCII Well, most people, when they start programming in C/C++, they would like to print something...
  3. On Waiting List of ChatGPT 4 API As of today, The ChatGPT-4 API Access is not yet available but we can request...
  4. Teaching Kids Programming – Max Profit of Rod Cutting (Unbounded Knapsack) via Bottom Up Dynamic Programming Algorithm Teaching Kids Programming: Videos on Data Structures and Algorithms You are given a list of...
  5. How to Fix a Slow/Incorrect Clock on Windows? I have been using HP Z800 Server for a couple of years and lately, the...
  6. Teaching Kids Programming – Geometry of Triangle Area and Side Law Teaching Kids Programming: Videos on Data Structures and Algorithms We know the area of triangle...
  7. Compute the Maximum Product of Three Numbers in an Array Given an array of integers – find out the maximum product of the tree numbers...
  8. Codeforces: B. Squares The problem is from codeforces: http://codeforces.com/contest/263/problem/B Sort the squares by sizes then we will easily derive...

Leave a Reply