Find regions with most common region size in a given boolean matrix
Given a boolean 2D array, arr[][] of size N*M where a group of connected 1s forms an island. Two cells are said to be connected if they are adjacent to each other horizontally, vertically, or diagonally. The task is to find the position of the top left corner of all the regions with the most common region size.
Examples:
Input: arr[][] = {{0, 0, 1, 1, 0},
{1, 0, 1, 1, 0},
{0, 0, 0, 0, 0},
{0, 0, 0, 0, 1}}
Output: {1, 0}, {3, 4}
Explanation: There are 3 regions, two with length 1 and the other with length 4. So the length of most common region is 1 and the positions of those regions are {1, 0}, {3, 4}.Input: arr[][] = {{0, 0, 1, 1, 0},
{0, 0, 1, 1, 0},
{0, 0, 0, 0, 0},
{0, 0, 0, 0, 1}}
Output: {0, 2}
Explanation: There are 2 regions, one with length 1 and the other with 4. Since both the regions have same frequency, both are the most common region. Hence, print position of any one of the regions.
Approach: The idea is based on the problem of finding the number of islands in Boolean 2D-matrix. The idea is to store the size of the regions along with their top-left corner position in a hashmap. And then iterate through the hashmap to find the most common region and print the required regions. Follow the steps below to solve the problem:
- Initialize a hashmap to store the size of the regions along with their top-left corner position.
- Maintain a visited array to keep track of all visited cells.
- Traverse the given 2D array, row-wise, and if the current element is ‘1’ and is not visited, perform DFS traversal from this node. After the traversal, store the size of the region in the map.
- After completing the above steps, iterate over the map to find the most common region and then print all the positions corresponding to the key in the map.
Below is the implementation of the above approach:
C++14
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; #define ROW 4 #define COL 5 // Function to check if a given cell // can be included in DFS int isSafe( int M[][COL], int row, int col, bool visited[][COL]) { return (row >= 0) && (row < ROW) && (col >= 0) && (col < COL) && (M[row][col] && !visited[row][col]); } // Utility function to do DFS for a 2D // boolean matrix void DFS( int M[][COL], int row, int col, bool visited[][COL], int & count) { // Initialize arrays 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); } } } // Function to find all the regions with most // common length in the given boolean 2D matrix void commonRegion( 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)); // Map to store the size and the regions unordered_map< int , vector<vector< int > > > um; // Traverse through the // all cells of given matrix for ( int i = 0; i < ROW; ++i) { for ( int j = 0; j < COL; ++j) { // If the current cell is 1 and is // not visited if (M[i][j] && !visited[i][j]) { // Increment count by 1 int count = 1; // Perform DFS DFS(M, i, j, visited, count); um[count].push_back({ i, j }); } } } // Store the most common region length int mostCommonRegion = 0; // Traverse the map to find the most common // region length for ( auto it = um.begin(); it != um.end(); it++) { int x = it->second.size(); mostCommonRegion = max(mostCommonRegion, x); } // Traverse the map to print the regions // having most common length for ( auto it = um.begin(); it != um.end(); it++) { int x = it->second.size(); if (mostCommonRegion == x) { // Print the top left position // of the regions for ( int i = 0; i < it->second.size(); i++) { int x = it->second[i][0]; int y = it->second[i][1]; cout << "{" << x << ", " << y << "}, " ; } break ; } } } // Driver code int main() { // Given Input int arr[][COL] = { { 0, 0, 1, 1, 0 }, { 1, 0, 1, 1, 0 }, { 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 1 } }; // Function call commonRegion(arr); return 0; } |
Python3
# Python program for the above approach ROW = 4 COL = 5 # Function to check if a given cell # can be included in DFS def isSafe(M, row, col, visited): if row < 0 : return False elif row > = ROW: return False elif col < 0 : return False elif col > = COL: return False elif M[row][col] = = 0 : return False elif visited[row][col] = = True : return False else : return True # Utility function to do DFS for a 2D # boolean matrix def DFS(M, row, col, visited): # Initialize arrays 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 count = 0 for k in range ( 8 ): if (isSafe(M, row + rowNbr[k], col + colNbr[k], visited) = = True ): # Increment region length by one count + = 1 count + = DFS(M, row + rowNbr[k], col + colNbr[k], visited) return count # Function to find all the regions with most # common length in the given boolean 2D matrix def commonRegion(M): # Make a bool array to mark visited cells, # initially all cells are unvisited visited = [[ False ] * COL] * ROW # Map to store the size and the regions um = {} # Traverse through the # all cells of given matrix for i in range (ROW): for j in range (COL): # If the current cell is 1 and is # not visited if ((M[i][j] = = 1 ) and (visited[i][j] = = False )): # Increment count by 1 count = 1 # Perform DFS count + = DFS(M, i, j, visited) if count in um.keys(): um[count].append([i, j]) else : um[count] = [[i, j]] # Store the most common region length mostCommonRegion = 0 # Traverse the map to find the most common # region length for it in um: x = len (um[it]) mostCommonRegion = max (mostCommonRegion, x) # Traverse the map to print the regions # having most common length for it in um: x = len (um[it]) if (mostCommonRegion = = x): # Print the top left position # of the regions for i in range (x): x = um[it][i][ 0 ] y = um[it][i][ 1 ] print ( "{" , x, ", " , y, "}, " ) break # Driver code # Given Input arr = [[ 0 , 0 , 1 , 1 , 0 ], [ 1 , 0 , 1 , 1 , 0 ], [ 0 , 0 , 0 , 0 , 0 ], [ 0 , 0 , 0 , 0 , 1 ]] # Function call commonRegion(arr) # This code is contributed by rj13to. |
C#
using System; using System.Collections.Generic; class GFG { static int ROW = 4; static int COL = 5; static bool isSafe( int [, ] M, int row, int col, bool [, ] visited) { return (row >= 0) && (row < ROW) && (col >= 0) && (col < COL) && (M[row, col] == 1 && !visited[row, col]); } static void DFS( int [, ] M, int row, int col, bool [, ] visited, ref int count) { int [] rowNbr = { -1, -1, -1, 0, 0, 1, 1, 1 }; int [] colNbr = { -1, 0, 1, -1, 1, -1, 0, 1 }; visited[row, col] = true ; for ( int k = 0; k < 8; ++k) { if (isSafe(M, row + rowNbr[k], col + colNbr[k], visited)) { count++; DFS(M, row + rowNbr[k], col + colNbr[k], visited, ref count); } } } static void commonRegion( int [, ] M) { bool [, ] visited = new bool [ROW, COL]; for ( int i = 0; i < ROW; ++i) { for ( int j = 0; j < COL; ++j) { visited[i, j] = false ; } } Dictionary< int , List<List< int > > > um = new Dictionary< int , List<List< int > > >(); for ( int i = 0; i < ROW; ++i) { for ( int j = 0; j < COL; ++j) { if (M[i, j] == 1 && !visited[i, j]) { int count = 1; DFS(M, i, j, visited, ref count); if (!um.ContainsKey(count)) { um[count] = new List<List< int > >(); } um[count].Add( new List< int >{ i, j }); } } } int mostCommonRegion = 0; foreach (KeyValuePair< int , List<List< int > > > entry in um) { int x = entry.Value.Count; mostCommonRegion = Math.Max(mostCommonRegion, x); } foreach (KeyValuePair< int , List<List< int > > > entry in um) { int x = entry.Value.Count; if (mostCommonRegion == x) { foreach (List< int > list in entry.Value) { int x1 = list[0]; int y1 = list[1]; Console.Write( "{" + x1 + ", " + y1 + "}, " ); } break ; } } } static void Main() { int [, ] arr = { { 0, 0, 1, 1, 0 }, { 1, 0, 1, 1, 0 }, { 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 1 } }; commonRegion(arr); } } |
Javascript
const ROW = 4; const COL = 5; function isSafe(M, row, col, visited) { if (row < 0) { return false ; } else if (row >= ROW) { return false ; } else if (col < 0) { return false ; } else if (col >= COL) { return false ; } else if (M[row][col] == 0) { return false ; } else if (visited[row][col] == true ) { return false ; } else { return true ; } } function DFS(M, row, col, visited) { const rowNbr = [-1, -1, -1, 0, 0, 1, 1, 1]; const colNbr = [-1, 0, 1, -1, 1, -1, 0, 1]; visited[row][col] = true ; let count = 0; for (let k = 0; k < 8; k++) { if (isSafe(M, row + rowNbr[k], col + colNbr[k], visited)) { count++; count += DFS(M, row + rowNbr[k], col + col |
Java
import java.util.*; public class Main { static int ROW = 4 ; static int COL = 5 ; // Function to check if a given cell // can be included in DFS static boolean isSafe( int [][] M, int row, int col, boolean [][] visited) { if (row < 0 ) { return false ; } else if (row >= ROW) { return false ; } else if (col < 0 ) { return false ; } else if (col >= COL) { return false ; } else if (M[row][col] == 0 ) { return false ; } else if (visited[row][col] == true ) { return false ; } else { return true ; } } // Utility function to do DFS for a 2D // boolean matrix static int DFS( int [][] M, int row, int col, boolean [][] visited) { // Initialize arrays 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 int count = 0 ; for ( int k = 0 ; k < 8 ; k++) { if (isSafe(M, row + rowNbr[k], col + colNbr[k], visited) == true ) { // Increment region length by one count += 1 ; count += DFS(M, row + rowNbr[k], col + colNbr[k], visited); } } return count; } // Function to find all the regions with most // common length in the given boolean 2D matrix static void commonRegion( int [][] M) { // Make a boolean array to mark visited cells, // initially all cells are unvisited boolean [][] visited = new boolean [ROW][COL]; // Map to store the size and the regions Map<Integer, List< int []> > um = new HashMap<>(); // Traverse through all cells of given matrix for ( int i = 0 ; i < ROW; i++) { for ( int j = 0 ; j < COL; j++) { // If the current cell is 1 and is not // visited if (M[i][j] == 1 && !visited[i][j]) { // Increment count by 1 int count = 1 ; // Perform DFS count += DFS(M, i, j, visited); if (um.containsKey(count)) { um.get(count).add( new int [] { i, j }); } else { List< int []> list = new ArrayList<>(); list.add( new int [] { i, j }); um.put(count, list); } } } } // Store the most common region length int mostCommonRegion = 0 ; // Traverse the map to find the most common region // length for ( int key : um.keySet()) { int x = um.get(key).size(); mostCommonRegion = Math.max(mostCommonRegion, x); } // Traverse the map to print the regions having most // common length for ( int key : um.keySet()) { int x = um.get(key).size(); if (mostCommonRegion == x) { // Print the top left position of the // regions List< int []> list = um.get(key); for ( int [] pos : list) { System.out.print( "{" + pos[ 0 ] + ", " + pos[ 1 ] + "}, " ); } break ; } } } // Driver code public static void main(String[] args) { // Given Input int [][] arr = { { 0 , 0 , 1 , 1 , 0 }, { 1 , 0 , 1 , 1 , 0 }, { 0 , 0 , 0 , 0 , 0 }, { 0 , 0 , 0 , 0 , 1 } }; // Function call commonRegion(arr); } } // Contributed by adityasha4x71 |
{1, 0}, {3, 4},
Time Complexity: O(N*M)
Auxiliary Space: O(N*M)