Find size of the largest region in Boolean Matrix

Last Updated : 30 Oct, 2023

Consider a matrix, where each cell contains either a ‘0’ or a ‘1’, and any cell containing a 1 is called a filled cell. Two cells are said to be connected if they are adjacent to each other horizontally, vertically, or diagonally. If one or more filled cells are also connected, they form a region. find the size of the largest region.

Examples:

Input: M[][]=
{{0,0,1,0,0,0,0,1,0,0,0,0,0},
{0,0,0,0,0,0,0,1,1,1,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,1,1,0,1,0,0,0,1,0,1,0,0},
{0,1,0,0,1,1,0,0,1,1,1,0,0},
{0,1,0,0,1,1,0,0,0,0,1,0,0},
{0,0,0,0,0,0,0,1,1,1,0,0,0},
{0,0,0,0,0,0,0,1,1,0,0,0,0}}
Ouptut: 11
Explanation: shown in the figure below:

Input: M[][5] = { {0, 0, 1, 1, 0}, {1, 0, 1, 1, 0}, {0, 1, 0, 0, 0}, {0, 0, 0, 0, 1}}
Output: 6
Explanation: In the following example, there are 2 regions.
One with size 1 and the other as 6. So largest region: 6

Approach: To solve the problem follow the below idea:

The idea is based on the problem of finding number of islands in Boolean 2D-matrix

Find the length of the largest region in Boolean Matrix using DFS:

Follow the given steps to solve the problem:

A cell in the 2D matrix can be connected to at most 8 neighbors.
So in DFS, make recursive calls for 8 neighbors of that cell.
- Keep a visited Hash-map to keep track of all visited cells.
- Also, keep track of the visited 1’s in every DFS and update the maximum size region.

Below is the implementation of the above approach:

C++

// C++ Program to find the length of the largest
// region in boolean 2D-matrix
#include <bits/stdc++.h>
using namespace std;
#define ROW 4
#define COL 5
 
// A function to check if
// a given cell (row, col)
// can be included in DFS
int isSafe(int M[][COL], int row, int col,
           bool visited[][COL])
{
    // row number is in range,
    // column number is in
    // range and value is 1
    // and not yet visited
    return (row >= 0) && (row < ROW) && (col >= 0)
           && (col < COL)
           && (M[row][col] && !visited[row][col]);
}
 
// A utility function to
// do DFS for a 2D boolean
// matrix. It only considers
// the 8 neighbours as
// adjacent vertices
void DFS(int M[][COL], int row, int col,
         bool visited[][COL], int& count)
{
    // These arrays are used
    // to get row and column
    // numbers of 8 neighbours
    // of a given cell
    static int rowNbr[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
    static int colNbr[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
 
    // Mark this cell as visited
    visited[row][col] = true;
 
    // Recur for all connected neighbours
    for (int k = 0; k < 8; ++k) {
        if (isSafe(M, row + rowNbr[k], col + colNbr[k],
                   visited)) {
            // Increment region length by one
            count++;
            DFS(M, row + rowNbr[k], col + colNbr[k],
                visited, count);
        }
    }
}
 
// The main function that returns
// largest  length region
// of a given boolean 2D matrix
int largestRegion(int M[][COL])
{
    // Make a bool array to mark visited cells.
    // Initially all cells are unvisited
    bool visited[ROW][COL];
    memset(visited, 0, sizeof(visited));
 
    // Initialize result as 0 and travesle through the
    // all cells of given matrix
    int result = INT_MIN;
    for (int i = 0; i < ROW; ++i) {
        for (int j = 0; j < COL; ++j) {
            // If a cell with value 1 is not
            if (M[i][j] && !visited[i][j]) {
                // visited yet, then new region found
                int count = 1;
                DFS(M, i, j, visited, count);
 
                // maximum region
                result = max(result, count);
            }
        }
    }
    return result;
}
 
// Driver code
int main()
{
    int M[][COL] = { { 0, 0, 1, 1, 0 },
                     { 1, 0, 1, 1, 0 },
                     { 0, 1, 0, 0, 0 },
                     { 0, 0, 0, 0, 1 } };
 
    // Function call
    cout << largestRegion(M);
 
    return 0;
}

Java

// Java program to find the length of the largest
// region in boolean 2D-matrix
import java.io.*;
import java.util.*;
 
class GFG {
    static int ROW, COL, count;
 
    // A function to check if a given cell (row, col)
    // can be included in DFS
    static boolean isSafe(int[][] M, int row, int col,
                          boolean[][] visited)
    {
        // row number is in range, column number is in
        // range and value is 1 and not yet visited
        return (
            (row >= 0) && (row < ROW) && (col >= 0)
            && (col < COL)
            && (M[row][col] == 1 && !visited[row][col]));
    }
 
    // A utility function to do DFS for a 2D boolean
    // matrix. It only considers the 8 neighbours as
    // adjacent vertices
    static void DFS(int[][] M, int row, int col,
                    boolean[][] visited)
    {
        // These arrays are used to get row and column
        // numbers of 8 neighbours of a given cell
        int[] rowNbr = { -1, -1, -1, 0, 0, 1, 1, 1 };
        int[] colNbr = { -1, 0, 1, -1, 1, -1, 0, 1 };
 
        // Mark this cell as visited
        visited[row][col] = true;
 
        // Recur for all connected neighbours
        for (int k = 0; k < 8; k++) {
            if (isSafe(M, row + rowNbr[k], col + colNbr[k],
                       visited)) {
                // increment region length by one
                count++;
                DFS(M, row + rowNbr[k], col + colNbr[k],
                    visited);
            }
        }
    }
 
    // The main function that returns largest length region
    // of a given boolean 2D matrix
    static int largestRegion(int[][] M)
    {
        // Make a boolean array to mark visited cells.
        // Initially all cells are unvisited
        boolean[][] visited = new boolean[ROW][COL];
 
        // Initialize result as 0 and traverse through the
        // all cells of given matrix
        int result = 0;
        for (int i = 0; i < ROW; i++) {
            for (int j = 0; j < COL; j++) {
 
                // If a cell with value 1 is not
                if (M[i][j] == 1 && !visited[i][j]) {
 
                    // visited yet, then new region found
                    count = 1;
                    DFS(M, i, j, visited);
 
                    // maximum region
                    result = Math.max(result, count);
                }
            }
        }
        return result;
    }
 
    // Driver code
    public static void main(String args[])
    {
        int M[][] = { { 0, 0, 1, 1, 0 },
                      { 1, 0, 1, 1, 0 },
                      { 0, 1, 0, 0, 0 },
                      { 0, 0, 0, 0, 1 } };
        ROW = 4;
        COL = 5;
 
        // Function call
        System.out.println(largestRegion(M));
    }
}
 
// This code is contributed by rachana soma

Python3

# Python3 program to find the length of the
# largest region in boolean 2D-matrix
 
# A function to check if a given cell
# (row, col) can be included in DFS
 
 
def isSafe(M, row, col, visited):
    global ROW, COL
 
    # row number is in range, column number is in
    # range and value is 1 and not yet visited
    return ((row >= 0) and (row < ROW) and
            (col >= 0) and (col < COL) and
            (M[row][col] and not visited[row][col]))
 
# A utility function to do DFS for a 2D
# boolean matrix. It only considers
# the 8 neighbours as adjacent vertices
 
 
def DFS(M, row, col, visited, count):
 
    # These arrays are used to get row and column
    # numbers of 8 neighbours of a given cell
    rowNbr = [-1, -1, -1, 0, 0, 1, 1, 1]
    colNbr = [-1, 0, 1, -1, 1, -1, 0, 1]
 
    # Mark this cell as visited
    visited[row][col] = True
 
    # Recur for all connected neighbours
    for k in range(8):
        if (isSafe(M, row + rowNbr[k],
                   col + colNbr[k], visited)):
 
            # increment region length by one
            count[0] += 1
            DFS(M, row + rowNbr[k],
                col + colNbr[k], visited, count)
 
# The main function that returns largest
# length region of a given boolean 2D matrix
 
 
def largestRegion(M):
    global ROW, COL
 
    # Make a bool array to mark visited cells.
    # Initially all cells are unvisited
    visited = [[0] * COL for i in range(ROW)]
 
    # Initialize result as 0 and traverse
    # through the all cells of given matrix
    result = -999999999999
    for i in range(ROW):
        for j in range(COL):
 
            # If a cell with value 1 is not
            if (M[i][j] and not visited[i][j]):
 
                # visited yet, then new region found
                count = [1]
                DFS(M, i, j, visited, count)
 
                # maximum region
                result = max(result, count[0])
    return result
 
 
# Driver Code
if __name__ == '__main__':
  ROW = 4
  COL = 5
 
  M = [[0, 0, 1, 1, 0],
       [1, 0, 1, 1, 0],
       [0, 1, 0, 0, 0],
       [0, 0, 0, 0, 1]]
 
  # Function call
  print(largestRegion(M))
 
# This code is contributed by PranchalK

C#

// C# program to find the length of
// the largest region in boolean 2D-matrix
using System;
 
class GFG {
    static int ROW, COL, count;
 
    // A function to check if a given cell
    // (row, col) can be included in DFS
    static Boolean isSafe(int[, ] M, int row, int col,
                          Boolean[, ] visited)
    {
        // row number is in range, column number is in
        // range and value is 1 and not yet visited
        return (
            (row >= 0) && (row < ROW) && (col >= 0)
            && (col < COL)
            && (M[row, col] == 1 && !visited[row, col]));
    }
 
    // A utility function to do DFS for a 2D boolean
    // matrix. It only considers the 8 neighbours as
    // adjacent vertices
    static void DFS(int[, ] M, int row, int col,
                    Boolean[, ] visited)
    {
        // These arrays are used to get row and column
        // numbers of 8 neighbours of a given cell
        int[] rowNbr = { -1, -1, -1, 0, 0, 1, 1, 1 };
        int[] colNbr = { -1, 0, 1, -1, 1, -1, 0, 1 };
 
        // Mark this cell as visited
        visited[row, col] = true;
 
        // Recur for all connected neighbours
        for (int k = 0; k < 8; k++) {
            if (isSafe(M, row + rowNbr[k], col + colNbr[k],
                       visited)) {
                // increment region length by one
                count++;
                DFS(M, row + rowNbr[k], col + colNbr[k],
                    visited);
            }
        }
    }
 
    // The main function that returns
    // largest length region of
    // a given boolean 2D matrix
    static int largestRegion(int[, ] M)
    {
        // Make a boolean array to mark visited cells.
        // Initially all cells are unvisited
        Boolean[, ] visited = new Boolean[ROW, COL];
 
        // Initialize result as 0 and traverse
        // through the all cells of given matrix
        int result = 0;
        for (int i = 0; i < ROW; i++) {
            for (int j = 0; j < COL; j++) {
                // If a cell with value 1 is not
                if (M[i, j] == 1 && !visited[i, j]) {
                    // visited yet,
                    // then new region found
                    count = 1;
                    DFS(M, i, j, visited);
 
                    // maximum region
                    result = Math.Max(result, count);
                }
            }
        }
        return result;
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        int[, ] M = { { 0, 0, 1, 1, 0 },
                      { 1, 0, 1, 1, 0 },
                      { 0, 1, 0, 0, 0 },
                      { 0, 0, 0, 0, 1 } };
        ROW = 4;
        COL = 5;
 
        // Function call
        Console.WriteLine(largestRegion(M));
    }
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
 
// JavaScript program to find the length of the largest
// region in boolean 2D-matrix
 
let ROW, COL, count;
 
// A function to check if a given cell (row, col)
    // can be included in DFS
function isSafe(M,row,col,visited)
{
    // row number is in range, column number is in
        // range and value is 1 and not yet visited
        return (
            (row >= 0) && (row < ROW) && (col >= 0)
            && (col < COL)
            && (M[row][col] == 1 && !visited[row][col]));
}
 
// A utility function to do DFS for a 2D boolean
    // matrix. It only considers the 8 neighbours as
    // adjacent vertices
function DFS(M,row,col,visited)
{
    // These arrays are used to get row and column
        // numbers of 8 neighbours of a given cell
        let rowNbr = [ -1, -1, -1, 0, 0, 1, 1, 1 ];
        let colNbr = [ -1, 0, 1, -1, 1, -1, 0, 1 ];
  
        // Mark this cell as visited
        visited[row][col] = true;
  
        // Recur for all connected neighbours
        for (let k = 0; k < 8; k++)
        {
            if (isSafe(M, row + rowNbr[k], col + colNbr[k],
                       visited))
            {
                // increment region length by one
                count++;
                DFS(M, row + rowNbr[k], col + colNbr[k],
                    visited);
            }
        }
}
 
// The main function that returns largest length region
    // of a given boolean 2D matrix
function largestRegion(M)
{
    // Make a boolean array to mark visited cells.
        // Initially all cells are unvisited
        let visited = new Array(ROW);
         for(let i=0;i<ROW;i++)
        {
            visited[i]=new Array(COL);
            for(let j=0;j<COL;j++)
            {
                visited[i][j]=false;
            }
        }
         
         
        // Initialize result as 0 and traverse through the
        // all cells of given matrix
        let result = 0;
        for (let i = 0; i < ROW; i++)
        {
            for (let j = 0; j < COL; j++)
            {
  
                // If a cell with value 1 is not
                if (M[i][j] == 1 && !visited[i][j])
                {
  
                    // visited yet, then new region found
                    count = 1;
                    DFS(M, i, j, visited);
  
                    // maximum region
                    result = Math.max(result, count);
                }
            }
        }
        return result;
}
 
// Driver code
let M=[[ 0, 0, 1, 1, 0 ],
                      [ 1, 0, 1, 1, 0 ],
                      [ 0, 1, 0, 0, 0 ],
                      [ 0, 0, 0, 0, 1 ] ];
                       
ROW = 4;
COL = 5;
 
// Function call
document.write(largestRegion(M));
 
 
// This code is contributed by avanitrachhadiya2155
 
</script>

Output

Time complexity: O(ROW * COL). In the worst case, all the cells will be visited so the time complexity is O(ROW * COL).
Auxiliary Space: O(ROW * COL). To store the visited nodes O(ROW * COL) space is needed.

Find the length of the largest region in Boolean Matrix using BFS:

Follow the given steps to solve the problem:

If the value at any particular cell is 1 then from here we need to do the BFS traversal
- Push the pair<i,j> in the queue
- Marking the value 1 to -1 so that we don’t again push the same cell again
- We will check in all 8 directions and if we encounter the cell having a value of 1 then we will push it into the queue and we will mark the cell to -1

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find unit area of the largest region of 1s.
 
int largestRegion(vector<vector<int> >& grid)
{
    int m = grid.size();
    int n = grid[0].size();
    // creating a queue that will help in bfs traversal
    queue<pair<int, int> > q;
    int area = 0;
    int ans = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            // if the value at any particular cell is 1 then
            // from here we need to do the BFS traversal
            if (grid[i][j] == 1) {
                ans = 0;
                // pushing the pair<i,j> in the queue
                q.push(make_pair(i, j));
                // marking the value 1 to -1 so that we
                // don't again push this cell in the queue
                grid[i][j] = -1;
                while (!q.empty()) {
 
                    pair<int, int> t = q.front();
                    q.pop();
                    ans++;
                    int x = t.first;
                    int y = t.second;
                    // now we will check in all 8 directions
                    if (x + 1 < m) {
                        if (grid[x + 1][y] == 1) {
                            q.push(make_pair(x + 1, y));
                            grid[x + 1][y] = -1;
                        }
                    }
                    if (x - 1 >= 0) {
                        if (grid[x - 1][y] == 1) {
                            q.push(make_pair(x - 1, y));
                            grid[x - 1][y] = -1;
                        }
                    }
                    if (y + 1 < n) {
                        if (grid[x][y + 1] == 1) {
                            q.push(make_pair(x, y + 1));
                            grid[x][y + 1] = -1;
                        }
                    }
                    if (y - 1 >= 0) {
                        if (grid[x][y - 1] == 1) {
                            q.push(make_pair(x, y - 1));
                            grid[x][y - 1] = -1;
                        }
                    }
                    if (x + 1 < m && y + 1 < n) {
                        if (grid[x + 1][y + 1] == 1) {
                            q.push(make_pair(x + 1, y + 1));
                            grid[x + 1][y + 1] = -1;
                        }
                    }
                    if (x - 1 >= 0 && y + 1 < n) {
                        if (grid[x - 1][y + 1] == 1) {
                            q.push(make_pair(x - 1, y + 1));
                            grid[x - 1][y + 1] = -1;
                        }
                    }
                    if (x - 1 >= 0 && y - 1 >= 0) {
                        if (grid[x - 1][y - 1] == 1) {
                            q.push(make_pair(x - 1, y - 1));
                            grid[x - 1][y - 1] = -1;
                        }
                    }
                    if (x + 1 < m && y - 1 >= 0) {
                        if (grid[x + 1][y - 1] == 1) {
                            q.push(make_pair(x + 1, y - 1));
                            grid[x + 1][y - 1] = -1;
                        }
                    }
                }
 
                area = max(ans, area);
                ans = 0;
            }
        }
    }
    return area;
}
 
// Driver Code
int main()
{
    vector<vector<int> > M = { { 0, 0, 1, 1, 0 },
                               { 1, 0, 1, 1, 0 },
                               { 0, 1, 0, 0, 0 },
                               { 0, 0, 0, 0, 1 } };
 
    // Function call
    cout << largestRegion(M);
    return 0;
}

Java

// Java program for the above approach
 
import java.io.*;
import java.util.*;
 
class GFG {
 
    private static class Pair {
        int x, y;
        Pair(int x, int y)
        {
            this.x = x;
            this.y = y;
        }
    }
 
    // Function to find unit area of the largest region of
    // 1s.
    private static int largestRegion(int M[][])
    {
        int m = M.length;
        int n = M[0].length;
 
        // creating a queue that will help in bfs traversal
        Queue<Pair> q = new LinkedList<>();
        int area = 0;
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // if the value at any particular cell is 1
                // then from here we need to do the BFS
                // traversal
                if (M[i][j] == 1) {
                    ans = 0;
 
                    // pushing the Pair(i,j) in the queue
                    q.offer(new Pair(i, j));
 
                    // marking the value 1 to -1 so that we
                    // don't again push this cell in the
                    // queue
                    M[i][j] = -1;
 
                    while (!q.isEmpty()) {
                        Pair t = q.poll();
                        ans++;
                        int x = t.x;
                        int y = t.y;
 
                        // now we will check in all 8
                        // directions
                        if (x + 1 < m) {
                            if (M[x + 1][y] == 1) {
                                q.offer(new Pair(x + 1, y));
                                M[x + 1][y] = -1;
                            }
                        }
                        if (x - 1 >= 0) {
                            if (M[x - 1][y] == 1) {
                                q.offer(new Pair(x - 1, y));
                                M[x - 1][y] = -1;
                            }
                        }
                        if (y + 1 < n) {
                            if (M[x][y + 1] == 1) {
                                q.offer(new Pair(x, y + 1));
                                M[x][y + 1] = -1;
                            }
                        }
                        if (y - 1 >= 0) {
                            if (M[x][y - 1] == 1) {
                                q.offer(new Pair(x, y - 1));
                                M[x][y - 1] = -1;
                            }
                        }
                        if (x + 1 < m && y + 1 < n) {
                            if (M[x + 1][y + 1] == 1) {
                                q.offer(
                                    new Pair(x + 1, y + 1));
                                M[x + 1][y + 1] = -1;
                            }
                        }
                        if (x - 1 >= 0 && y + 1 < n) {
                            if (M[x - 1][y + 1] == 1) {
                                q.offer(
                                    new Pair(x - 1, y + 1));
                                M[x - 1][y + 1] = -1;
                            }
                        }
                        if (x - 1 >= 0 && y - 1 >= 0) {
                            if (M[x - 1][y - 1] == 1) {
                                q.offer(
                                    new Pair(x - 1, y - 1));
                                M[x - 1][y - 1] = -1;
                            }
                        }
                        if (x + 1 < m && y - 1 >= 0) {
                            if (M[x + 1][y - 1] == 1) {
                                q.offer(
                                    new Pair(x + 1, y - 1));
                                M[x + 1][y - 1] = -1;
                            }
                        }
                    }
 
                    area = Math.max(area, ans);
                    ans = 0;
                }
            }
        }
        return area;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int M[][] = { { 0, 0, 1, 1, 0 },
                      { 1, 0, 1, 1, 0 },
                      { 0, 1, 0, 0, 0 },
                      { 0, 0, 0, 0, 1 } };
 
        // Function call
        System.out.println(largestRegion(M));
    }
}
 
// This code is contributed by Snigdha Patil

Python3

from typing import List, Tuple
from collections import deque
 
def largestRegion(grid: List[List[int]]) -> int:
    m = len(grid)
    n = len(grid[0])
 
    # creating a queue that will help in bfs traversal
    q = deque()
    area = 0
    ans = 0
    for i in range(m):
        for j in range(n):
            # if the value at any particular cell is 1 then
            # from here we need to do the BFS traversal
            if grid[i][j] == 1:
                ans = 0
                # pushing the pair(i,j) in the queue
                q.append((i, j))
                # marking the value 1 to -1 so that we
                # don't again push this cell in the queue
                grid[i][j] = -1
                while len(q) > 0:
                    t = q.popleft()
                    ans += 1
                    x, y = t[0], t[1]
                    # now we will check in all 8 directions
                    if x + 1 < m:
                        if grid[x + 1][y] == 1:
                            q.append((x + 1, y))
                            grid[x + 1][y] = -1
                    if x - 1 >= 0:
                        if grid[x - 1][y] == 1:
                            q.append((x - 1, y))
                            grid[x - 1][y] = -1
                    if y + 1 < n:
                        if grid[x][y + 1] == 1:
                            q.append((x, y + 1))
                            grid[x][y + 1] = -1
                    if y - 1 >= 0:
                        if grid[x][y - 1] == 1:
                            q.append((x, y - 1))
                            grid[x][y - 1] = -1
                    if x + 1 < m and y + 1 < n:
                        if grid[x + 1][y + 1] == 1:
                            q.append((x + 1, y + 1))
                            grid[x + 1][y + 1] = -1
                    if x - 1 >= 0 and y + 1 < n:
                        if grid[x - 1][y + 1] == 1:
                            q.append((x - 1, y + 1))
                            grid[x - 1][y + 1] = -1
                    if x - 1 >= 0 and y - 1 >= 0:
                        if grid[x - 1][y - 1] == 1:
                            q.append((x - 1, y - 1))
                            grid[x - 1][y - 1] = -1
                    if x + 1 < m and y - 1 >= 0:
                        if grid[x + 1][y - 1] == 1:
                            q.append((x + 1, y - 1))
                            grid[x + 1][y - 1] = -1
                area = max(area, ans)
    return area
 
def main():
    grid = [
        [0, 0, 1, 1, 0],
        [1, 0, 1, 1, 0],
        [0, 1, 0, 0, 0],
        [0, 0, 0, 0, 1]
    ]
    result = largestRegion(grid)
    print(f'Largest region of 1s has an area of {result}')
 
main()

C#

// C# program for the above approach
 
using System;
using System.Collections.Generic;
 
class Program
{
// Function to find unit area of the largest region of 1s.
public static int LargestRegion(List<List<int>> grid)
{
    int m = grid.Count;
    int n = grid[0].Count;
    // creating a queue that will help in bfs traversal
    Queue<Tuple<int, int>> q = new Queue<Tuple<int, int>>();
    int area = 0;
    int ans = 0;
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            // if the value at any particular cell is 1 then
            // from here we need to do the BFS traversal
            if (grid[i][j] == 1)
            {
                ans = 0;
                // pushing the Tuple<i,j> in the queue
                q.Enqueue(Tuple.Create(i, j));
                // marking the value 1 to -1 so that we
                // don't again push this cell in the queue
                grid[i][j] = -1;
                while (q.Count != 0)
                {
                    Tuple<int, int> t = q.Dequeue();
                    ans++;
                    int x = t.Item1;
                    int y = t.Item2;
                    // now we will check in all 8 directions
                    if (x + 1 < m)
                    {
                        if (grid[x + 1][y] == 1)
                        {
                            q.Enqueue(Tuple.Create(x + 1, y));
                            grid[x + 1][y] = -1;
                        }
                    }
                    if (x - 1 >= 0)
                    {
                        if (grid[x - 1][y] == 1)
                        {
                            q.Enqueue(Tuple.Create(x - 1, y));
                            grid[x - 1][y] = -1;
                        }
                    }
                    if (y + 1 < n)
                    {
                        if (grid[x][y + 1] == 1)
                        {
                            q.Enqueue(Tuple.Create(x, y + 1));
                            grid[x][y + 1] = -1;
                        }
                    }
                    if (y - 1 >= 0)
                    {
                        if (grid[x][y - 1] == 1)
                        {
                            q.Enqueue(Tuple.Create(x, y - 1));
                            grid[x][y - 1] = -1;
                        }
                    }
                    if (x + 1 < m && y + 1 < n)
                    {
                        if (grid[x + 1][y + 1] == 1)
                        {
                            q.Enqueue(Tuple.Create(x + 1, y + 1));
                            grid[x + 1][y + 1] = -1;
                        }
                    }
                    if (x - 1 >= 0 && y + 1 < n)
                    {
                        if (grid[x - 1][y + 1] == 1)
{
q.Enqueue(Tuple.Create(x - 1, y + 1));
grid[x - 1][y + 1] = -1;
}
}
if (x - 1 >= 0 && y - 1 >= 0)
{
if (grid[x - 1][y - 1] == 1)
{
q.Enqueue(Tuple.Create(x - 1, y - 1));
grid[x - 1][y - 1] = -1;
}
}
if (x + 1 < m && y - 1 >= 0)
{
if (grid[x + 1][y - 1] == 1)
{
q.Enqueue(Tuple.Create(x + 1, y - 1));
grid[x + 1][y - 1] = -1;
}
}
}
area = Math.Max(area, ans);
}
}
}
return area;
}
 
// Driver code
public static void Main()
{
List<List<int>> grid = new List<List<int>>();
grid.Add(new List<int> { 1, 1, 0, 0, 0 });
grid.Add(new List<int> { 0, 1, 1, 0, 0 });
grid.Add(new List<int> { 0, 0, 1, 0, 1 });
grid.Add(new List<int> { 1, 0, 0, 0, 1 });
grid.Add(new List<int> { 0, 1, 0, 1, 1 });
Console.WriteLine(LargestRegion(grid));
}
}
 
//This code is contributed by shivamsharma215

Javascript

// Javascript program for the above approach
 
     // program to implement queue data structure
     class Queue {
       constructor() {
         this.items = Array.from(Array(), () => new Array());
       }
 
       // add element to the queue
       push(element) {
         return this.items.push(element);
       }
 
       // remove element from the queue
       pop() {
         if (this.items.length > 0) {
           return this.items.shift();
         }
       }
 
       // view the first element
       front() {
         return this.items[0];
       }
 
       // check if the queue is empty
       empty() {
         return this.items.length == 0;
       }
     }
 
     // Function to find unit area of the largest region of 1s.
 
     function largestRegion(grid) {
       let m = grid.length;
       let n = grid[0].length;
       // creating a queue that will help in bfs traversal
       let q = new Queue();
       let area = 0;
       let ans = 0;
       for (let i = 0; i < m; i++) {
         for (let j = 0; j < n; j++) {
           // if the value at any particular cell is 1 then
           // from here we need to do the BFS traversal
           if (grid[i][j] == 1) {
             ans = 0;
 
             // pushing the pair<i,j> in the queue
             q.push([i, j]);
             // marking the value 1 to -1 so that we
             // don't again push this cell in the queue
             grid[i][j] = -1;
             while (!q.empty()) {
               t = q.front();
               q.pop();
               ans++;
 
               let x = t[0];
               let y = t[1];
 
               // now we will check in all 8 directions
               if (x + 1 < m) {
                 if (grid[x + 1][y] == 1) {
                   q.push([x + 1, y]);
                   grid[x + 1][y] = -1;
                 }
               }
               if (x - 1 >= 0) {
                 if (grid[x - 1][y] == 1) {
                   q.push([x - 1, y]);
                   grid[x - 1][y] = -1;
                 }
               }
               if (y + 1 < n) {
                 if (grid[x][y + 1] == 1) {
                   q.push([x, y + 1]);
                   grid[x][y + 1] = -1;
                 }
               }
               if (y - 1 >= 0) {
                 if (grid[x][y - 1] == 1) {
                   q.push([x, y - 1]);
                   grid[x][y - 1] = -1;
                 }
               }
               if (x + 1 < m && y + 1 < n) {
                 if (grid[x + 1][y + 1] == 1) {
                   q.push([x + 1, y + 1]);
                   grid[x + 1][y + 1] = -1;
                 }
               }
               if (x - 1 >= 0 && y + 1 < n) {
                 if (grid[x - 1][y + 1] == 1) {
                   q.push([x - 1, y + 1]);
                   grid[x - 1][y + 1] = -1;
                 }
               }
               if (x - 1 >= 0 && y - 1 >= 0) {
                 if (grid[x - 1][y - 1] == 1) {
                   q.push([x - 1, y - 1]);
                   grid[x - 1][y - 1] = -1;
                 }
               }
               if (x + 1 < m && y - 1 >= 0) {
                 if (grid[x + 1][y - 1] == 1) {
                   q.push([x + 1, y - 1]);
                   grid[x + 1][y - 1] = -1;
                 }
               }
             }
             area = Math.max(ans, area);
             ans = 0;
           }
         }
       }
       return area;
     }
 
     // Driver Code
     M = [
       [0, 0, 1, 1, 0],
       [1, 0, 1, 1, 0],
       [0, 1, 0, 0, 0],
       [0, 0, 0, 0, 1],
     ];
 
     // Function call
     console.log(largestRegion(M));

Output

Time complexity: O(ROW * COL). In the worst case, all the cells will be visited so the time complexity is O(ROW * COL).
Auxiliary Space: O(ROW * COL). Space used by queue to apply BFS

This article is contributed by Nishant Singh.

Nishant Singh

Improve

Minimum steps to reach a destination

Longest path between any pair of vertices

DFS in different language

Variations of DFS implementations

Graph Algorithms that uses DFS

Easy problems on DFS

Medium problems on DFS

Hard problems on DFS

Find size of the largest region in Boolean Matrix

Find the length of the largest region in Boolean Matrix using DFS:

C++

Java

Python3

C#

Javascript

Find the length of the largest region in Boolean Matrix using BFS:

C++

Java

Python3

C#

Javascript

Please Login to comment...

Similar Reads

What kind of Experience do you want to share?