# 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:

Approach: Using DFS

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;                    Queue<int[]> queue = 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