Size of the largest region in Boolean Matrix
Given a matrix where each cell contains either a '0' or a '1', we define a "filled cell" as any cell containing a '1'. Cells are considered connected if they are adjacent to each other horizontally, vertically, or diagonally. A group of connected filled cells constitutes a "region". The task is to determine the size of the largest region within the matrix.
Example 1:
![Size of the largest region in Boolean Matrix/>
<!-- /wp:html -->
<!-- wp:paragraph -->
<p><strong>Input: </strong>Int M[][] = { {0, 0, 1, 1, 0}, {1, 0, 1, 1, 0}, {0, 1, 0, 0, 0}, {0, 0, 0, 0, 1}}</p>
<!-- /wp:paragraph -->
<!-- wp:paragraph -->
<p><strong>Output: </strong>The size of the largest region in the boolean matrix is 6.</p>
<!-- /wp:paragraph -->
<!-- wp:paragraph -->
<p><strong>Explanation: </strong>The graph shows we have the largest region size is 6.</p>
<!-- /wp:paragraph -->
<!-- wp:heading -->
<h2 class=](https://static.tutorialandexample.com/java/size-of-the-largest-region-in-boolean-matrix1.png)
In this approach, we use depth-first search (DFS) to traverse a given matrix. We iterate through each cell of the matrix, marking visited cells to avoid redundancy. For each unvisited '1' cell, it recursively explores all adjacent '1' cells using DFS, calculating the size of each connected region. The maximum region size encountered is continuously updated and returned at the end.
FileName: LargestRegionSize.java
public class LargestRegionSize { // Function to perform DFS traversal from a given cell private static int dfs(int[][] matrix, int row, int col, boolean[][] visited) { // Define the directions (horizontally, vertically, and diagonally) int[] dr = {-1, -1, -1, 0, 0, 1, 1, 1}; int[] dc = {-1, 0, 1, -1, 1, -1, 0, 1}; // Mark the current cell as visited visited[row][col] = true; int size = 1; // Explore all adjacent cells for (int i = 0; i < 8; i++) { int newRow = row + dr[i]; int newCol = col + dc[i]; // Check if the adjacent cell is within bounds and contains '1' if (newRow >= 0 && newRow < matrix.length && newCol >= 0 && newCol < matrix[0].length && matrix[newRow][newCol] == 1 && !visited[newRow][newCol]) { // Recursively perform DFS on the adjacent cell size += dfs(matrix, newRow, newCol, visited); } } return size; } // Function to find the size of the largest region public static int largestRegionSize(int[][] matrix) { int maxRegionSize = 0; int rows = matrix.length; int cols = matrix[0].length; // Initialize a boolean array to keep track of visited cells boolean[][] visited = new boolean[rows][cols]; // Iterate through each cell in the matrix for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { // If the cell contains '1' and has not been visited yet, perform DFS if (matrix[i][j] == 1 && !visited[i][j]) { int regionSize = dfs(matrix, i, j, visited); // Update the maximum region size if a larger region is found if (regionSize > maxRegionSize) { maxRegionSize = regionSize; } } } } return maxRegionSize; } public static void main(String[] args) { int[][] matrix = { {1, 1, 0, 0, 1}, {0, 0, 1, 1, 0}, {1, 0, 0, 0, 1}, {1, 1, 1, 0, 0} }; int largestRegion = largestRegionSize(matrix); System.out.println("Size of the largest region: " + largestRegion); } }
Output:
Size of the largest region: 6
Complexity Analysis:
Time Complexity: O(rows * cols), The complexity is because of the iteration of the boolean matrix.
Space Complexity: O(rows * cols), The complexity is because of the storing the values of the boolean matrix
Approach: Using BFS
In this approach, we use Breadth-First Search (BFS) to traverse a given matrix. We iterate through each cell, marking visited cells to avoid redundancy. For each unvisited '1' cell, it performs BFS to explore all adjacent '1' cells and calculate the size of the region. The maximum region size encountered is continuously updated. Finally, we return the size of the largest region.
FileName: LargestRegionSize.java
import java.util.LinkedList; import java.util.Queue; public class LargestRegionSize { // Function to find the size of the largest region using Breadth-First Search (BFS) public static int largestRegionSize(int[][] matrix) { int maxRegionSize = 0; int rows = matrix.length; int cols = matrix[0].length; // Initialize a boolean array to keep track of visited cells boolean[][] visited = new boolean[rows][cols]; // Define the directions (horizontally, vertically, and diagonally) int[] dr = {-1, -1, -1, 0, 0, 1, 1, 1}; int[] dc = {-1, 0, 1, -1, 1, -1, 0, 1}; // Iterate through each cell in the matrix for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { // If the cell contains '1' and has not been visited yet, perform BFS if (matrix[i][j] == 1 && !visited[i][j]) { int regionSize = 0; Queuequeue = new LinkedList<>(); queue.offer(new int[]{i, j}); visited[i][j] = true; while (!queue.isEmpty()) { int[] currentCell = queue.poll(); int currentRow = currentCell[0]; int currentCol = currentCell[1]; regionSize++; // Explore all adjacent cells for (int k = 0; k < 8; k++) { int newRow = currentRow + dr[k]; int newCol = currentCol + dc[k]; // Check if the adjacent cell is within bounds and contains '1' if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && matrix[newRow][newCol] == 1 && !visited[newRow][newCol]) { queue.offer(new int[]{newRow, newCol}); visited[newRow][newCol] = true; } } } // Update the maximum region size if a larger region is found if (regionSize > maxRegionSize) { maxRegionSize = regionSize; } } } } return maxRegionSize; } public static void main(String[] args) { int[][] matrix = { {1, 1, 0, 0, 1}, {0, 0, 1, 1, 0}, {1, 0, 0, 0, 1}, {1, 1, 1, 0, 0} }; int largestRegion = largestRegionSize(matrix); System.out.println("Size of the largest region: " + largestRegion); } }
Output:
Size of the largest region: 6
Complexity Analysis:
Time Complexity: O(rows * cols), The complexity is because of the iteration of the boolean matrix.
Space Complexity: O(rows * cols), The complexity is because of the storing the values of the boolean matrix