A boolean matrix is a matrix whose entries are boolean values, i.e., either 0 or 1. When the two-element boolean algebra is used, it is known as a logical matrix. In this blog, we will find the length of the largest region in the boolean matrix.
Let's get started.
Problem statement🕵️♂️
Consider a matrix with columns and rows, where every cell has either '0' or '1'. A cell containing 1 is considered a filled cell. Two cells are referred to be connected if they are adjacent horizontally, diagonally, or vertically. A region is formed when one or more filled cells are connected. We have to find the length of the largest region in the Boolean matrix.
Input: You are given an NxM matrix of a positive integer, where the value is either ‘0’ or ‘1’.
Output: An integer representing the length of the largest region in the boolean matrix.
Here, as we can see, only one filled cell is present in region one, while in region 2, there are 7 connected filled cells. Therefore, the output will be 7. This way, we will find the length of the largest region in the Boolean matrix.
Approach👩💻
📝DFS Approach
To solve this problem, we have to follow the DFS approach. The steps for this are as follows:
In a 2D matrix, a cell can be connected to a maximum of 8 neighbor cells.
Therefore in DFS, we will make recursive calls for eight neighbors of that cell.
✳️Store a visited hash map to keep note of all visited cells.
✳️ In addition, we will have to keep track of the visited 1's in each DGS and update the max size of the region.
📝 BFS Approach
Another approach with which we can solve this problem is the BFS approach; the steps are as follows:
In this approach, we will start the BFS traversal from the cell whose value will be 1.
✳️ We will first put the pair <i,j> in the queue.
✳️ We will mark the value from 1 to -1 so we don't revisit the visited cell.
✳️ We will check in all the eight neighbor's directions. If we find the cell having a value of 1, then we will push the cell into the queue. And the cell will be marked as -1.
Solution
🙇♀️Solution by DFS Approach
🔥C++
#include <bits/stdc++.h>
using namespace std;
#define ROW 4
#define COL 5
int isNotVisited(int Mat[][COL], int row, int col, bool visited[][COL]) {
return (row >= 0) && (row < ROW) && (col < COL) && (col >= 0 ) &&(Mat[row][col] && !visited[row][col]);
}
void DFS(int Mat[][COL], int row, int col, bool visited[][COL], int& count){
static int rowNumber[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
static int colNumber[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
visited[row][col] = true;
for (int k = 0; k < 8; ++k) {
if (isNotVisited(Mat, row + rowNumber[k], col + colNumber[k], visited)) {
count++;
DFS(Mat, row + rowNumber[k], col + colNumber[k], visited, count);
}
}
}
int findLargestRegion(int Mat[][COL]) {
bool isvisited[ROW][COL];
memset(isvisited, 0, sizeof(isvisited));
int maxCount = -1;
for (int i = 0; i < ROW; ++i) {
for (int j = 0; j < COL; ++j) {
if (Mat[i][j] && !isvisited[i][j]) {
int count = 1;
DFS(Mat, i, j, isvisited, count);
maxCount = max(maxCount, count);
}
}
}
return maxCount;
}
int main(){
int Mat[][COL] = { {0, 0, 1, 0, 1},
{0, 1, 1, 0, 0},
{1, 0, 1, 1, 0},
{0, 0, 0, 0, 1} };
cout<<"The length of largest region in Boolean matrix is "<<findLargestRegion(Mat);
return 0;
}
You can also try this code with Online C++ Compiler
The length of largest region in Boolean matrix is 7
🔥Python
def isNotVisited(Mat,row,col, visited):
global ROW,COL
# row number and column number is in
# range and value is 1 and not visited yet
return ((row >= 0) and (row < ROW) and
(col >= 0) and (col < COL) and
(Mat[row][col] and not visited[row][col]))
# A function to do DFS for a 2D
# boolean matrix. It only considers
# the eight neighbors as adjacent vertices.
def DFS(Mat, row, col, visited, count):
rowNumber = [-1, -1, -1, 0, 0, 1, 1, 1]
colNumber = [-1, 0, 1, -1, 1, -1, 0, 1]
# Mark this cell as visited
visited[row][col] = True
# Recur for all connected neighbors
for k in range(8):
if (isNotVisited(Mat, row + rowNumber[k],
col + colNumber[k], visited)):
# increment region length by one
count[0] += 1
DFS(Mat, row + rowNumber[k],
col + colNumber[k], visited, count)
# The primary Function that returns the largest
# length region of a given 2D boolean matrix
def findlargestRegion(Mat):
global ROW, COL
# Make a boolean type array to note visited cells.
# Initially all cells are notvisited
visited = [[0] * COL for i in range(ROW)]
# Initializing res = 0 and traverse
# through all cells of a boolean matrix
res = -999999999999
for i in range(ROW):
for j in range(COL):
if (Mat[i][j] and not visited[i][j]):
# visited yet, then new region found
count = [1]
DFS(Mat, i, j, visited, count)
# maximum region
res = max(res, count[0])
return res
# Driver Code
if __name__ == '__main__':
ROW = 4
COL = 5
Mat = [[0, 0, 1, 0, 1],
[1, 1, 1, 1, 0],
[0, 1, 0, 0, 0],
[0, 0, 0, 1, 1]]
# Function call
print("The length of the largest region in the Boolean Matrix is:")
print(findlargestRegion(Mat))
You can also try this code with Online Python Compiler
The length of the largest region in Boolean Matrix is:
7
🔥 Java
import java.io.*;
import java.util.*;
class Ninjas {
static int ROW, count, COL;
/* to check if a cell ( col, row)
can be included in DFS */
static boolean isNotVisited(int[][] Mat, int row, int col,
boolean[][] visited)
{
/* row number is in range and column number is in
range and value is 1 and not visited yet */
return (
(row >= 0) && (row < ROW) && (col >= 0)
&& (col < COL)
&& (Mat[row][col] == 1 && !visited[row][col]));
}
/* A utility function to do DFS traversal for a 2D boolean
matrix. It only considers the eight neighbors as
adjacent vertices */
static void DFS(int[][] Mat, int row, int col,
boolean[][] visited)
{
/* These arrays are used to get column and row
numbers of eight neighbors of a given cell */
int[] rowNumber = { -1, -1, -1, 0, 0, 1, 1, 1 };
int[] colNumber = { -1, 0, 1, -1, 1, -1, 0, 1 };
/* Mark this cell as visited */
visited[row][col] = true;
/* Recur for all connected neighbors */
for (int k = 0; k < 8; k++) {
if (isNotVisited(Mat, row + rowNumber[k], col + colNumber[k],
visited)) {
/* increment region length by one */
count++;
DFS(Mat, row + rowNumber[k], col + colNumber[k],
visited);
}
}
}
/* The main Function that returns the largest length region
of a given boolean 2D matrix */
static int findlargestRegion(int[][] Mat)
{
/* Make a boolean array to note visited cells.
Initially all cells are unvisited */
boolean[][] visited = new boolean[ROW][COL];
/* Initialize the result as 0 and traverse through the
all cells of a given matrix */
int result = 0;
/*for loop */
for (int i = 0; i < ROW; i++) {
for (int j = 0; j < COL; j++) {
if (Mat[i][j] == 1 && !visited[i][j]) {
/* visited yet, then new region found */
count = 1;
DFS(Mat, i, j, visited);
/* maximum region */
result = Math.max(result, count);
}
}
}
return result;
}
/* Driver code */
public static void main(String args[])
{
int Mat[][] = { { 0, 0, 1, 0, 1 },
{ 1, 1, 1, 0, 0 },
{ 1, 0, 1, 1, 0 },
{ 0, 0, 0, 0, 1 } };
ROW = 4;
COL = 5;
/* Function call */
System.out.println("The length of the largest region in Boolean Matrix is:");
System.out.println(findlargestRegion(Mat));
}
}
You can also try this code with Online Java Compiler
The length of largest region in Boolean matrix is:7
🔥 Java
import java.io.*;
import java.util.*;
class Ninja {
private static class Pair {
int u, v;
Pair(int u, int v)
{
this.u = u;
this.v = v;
}
}
//Function to find the unit area of the largest region of
// 1s.
private static int findlargestRegion(int Mat[][])
{
int m = Mat.length;
int n = Mat[0].length;
// creating a queue for BFS traversal
Queue<Pair> q = new LinkedList<>();
int region = 0;
int ans = 0;
//for loop
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (Mat[i][j] == 1) {
ans = 0;
// pushing Pair(i,j) in the queue
q.offer(new Pair(i, j));
// noting the value 1 to -1 so that we
//don't push this cell in the
// queue again
Mat[i][j] = -1;
while (!q.isEmpty()) {
Pair t = q.poll();
ans++;
int u = t.u;
int v = t.v;
// now, we will check in all 8
// directions
if (u + 1 < m) {
if (Mat[u + 1][v] == 1) {
q.offer(new Pair(u + 1, v));
Mat[u + 1][v] = -1;
}
}
if (u - 1 >= 0) {
if (Mat[u - 1][v] == 1) {
q.offer(new Pair(u - 1, v));
Mat[u - 1][v] = -1;
}
}
if (v + 1 < n) {
if (Mat[u][v + 1] == 1) {
q.offer(new Pair(u, v + 1));
Mat[u][v + 1] = -1;
}
}
if (v - 1 >= 0) {
if (Mat[u][v - 1] == 1) {
q.offer(new Pair(u, v - 1));
Mat[u][v - 1] = -1;
}
}
if (u + 1 < m && v + 1 < n) {
if (Mat[u + 1][v + 1] == 1) {
q.offer(
new Pair(u + 1, v + 1));
Mat[u + 1][v + 1] = -1;
}
}
if (u - 1 >= 0 && v + 1 < n) {
if (Mat[u - 1][v + 1] == 1) {
q.offer(
new Pair(u - 1, v + 1));
Mat[u - 1][v + 1] = -1;
}
}
if (u - 1 >= 0 && v - 1 >= 0) {
if (Mat[u - 1][v - 1] == 1) {
q.offer(
new Pair(u - 1, v - 1));
Mat[u - 1][v - 1] = -1;
}
}
if (u + 1 < m && v - 1 >= 0) {
if (Mat[u + 1][v - 1] == 1) {
q.offer(
new Pair(u + 1, v - 1));
Mat[u + 1][v - 1] = -1;
}
}
}
region = Math.max(region, ans);
ans = 0;
}
}
}
return region;
}
// Driver Code
public static void main(String[] args)
{
int Mat[][] = { { 0, 0, 1, 0, 1 },
{ 0, 1, 1, 0, 0 },
{ 1, 0, 1, 1, 0 },
{ 0, 0, 0, 0, 1 } };
// Function call
System.out.println("The length of the largest region in Boolean matrix is:" +findlargestRegion(Mat) );
}
}
You can also try this code with Online Java Compiler
A boolean matrix is whose entries are boolean values, i.e., either 0 or 1.
What is BFS?
The shortest path in a graph is decided using a vertex-based approach known as Breadth-First Search (BFS).BFS visits and marks one vertex at the moment, and then its neighbors are visited and added to the queue. It takes longer to complete than DFS.
What is the difference between a DFS Traversal and a BFS Traversal?
In a DFS traversal of a graph, we begin from any random node and travel down each branch as far as feasible before returning to the current node. In contrast, in a BFS traversal, we visit each node before visiting their children's nodes.
Why does DFS require a stack?
When a search runs into a dead end during any iteration, the Depth-First Search (DFS) algorithm employs a stack to keep track of where to go next to continue the search.
What is the purpose of a depth-first search?
An algorithm for navigating or searching through tree or graph data structures is called depth-first search (DFS). The algorithm starts from the root node and proceeds to investigate each branch as far as it can go before turning around.
Conclusion
In this article, we have discussed the code to find the length of the largest region in the Boolean matrix. We started with the problem statement, approach, and solution to the problem of finding the length of the largest region in the Boolean matrix.
8+ registered 