Queries to find number of connected grid components of given sizes in a Matrix

Last Updated : 23 Jul, 2025

Given a matrix mat[][] containing only of 0s and 1s, and an array queries[], the task is for each query, say k, is to find the number of connected grid components (cells consisting of 1s) of size k.
Note: Two cells are connected if they share an edge in the direction up, down, left, and right not diagonal.

Example:

Input: mat[][] = [[1 1 1 1 1 1],
[1 1 0 0 0 0],
[0 0 0 1 1 1],
[0 0 0 1 1 1],
[0 0 1 0 0 0],
[1 0 0 0 0 0]]
queries[] = [6, 1, 8, 2]
Output: [1, 2, 1, 0]
Explanation: There are 4 connected components of sizes 8, 6, 1, 1 respectively hence the output the queries array is [1, 2, 1, 0]. We can see that the number of connected components of different sizes are marked down in the image:

Input: matrix[][] = [[1 1 0 0 0],
[1 0 0 1 0],
[0 0 1 1 0],
[1 1 0 0 0]]
queries[]= [3, 1, 2, 4]
Output: [2, 0, 1, 0]
Explanation: The number of connected components of sizes 3, 2 are 2, 1 all other sizes are zero hence the output array is [2, 0, 1, 0]

Approach: The idea is to count and store frequency of the number of connected components of ones of all sizes in a unordered map using BFS/DFS in the grid, then we can iterate over the queries array and assign the count of connected component for each given size in the array.
Following are the steps to solve the problem:

Iterate through matrix and perform BFS from the unvisited cell which contains "1"
Check if the unvisited valid adjacent cells contains 1 and push these cells in the queue.
Repeat the above two steps for all unvisited cells having 1 in them.
Print the array having the number of connected components for each given size in the queries.

Below is the implementation of the above approach:

C++

// C++ implementation for the above approach #include <bits/stdc++.h> using namespace std; const int n = 6; const int m = 6; const int dx[] = { 0, 1, -1, 0 }; const int dy[] = { 1, 0, 0, -1 }; // stores information about which cell // are already visited in a particular BFS int visited[n][m]; // Stores the count of cells in // the largest connected component int COUNT; // Function checks if a cell is valid, i.e. // it is inside the grid and equal to 1 bool is_valid(int x, int y, int matrix[n][m]) {  if (x < n && y < m && x >= 0 && y >= 0) {  if (visited[x][y] == false  && matrix[x][y] == 1)  return true;  else  return false;  }  else  return false; } // Map to count the frequency of // each connected component map<int, int> mp; // function to calculate the // largest connected component void findComponentSize(int matrix[n][m]) {  // Iterate over every cell  for (int i = 0; i < n; i++) {  for (int j = 0; j < m; j++) {  if (!visited[i][j] && matrix[i][j] == 1) {  COUNT = 0;  // Stores the indices of the matrix cells  queue<pair<int, int> > q;  // Mark the starting cell as visited  // and push it into the queue  q.push({ i, j });  visited[i][j] = true;  // Iterate while the queue  // is not empty  while (!q.empty()) {  pair<int, int> p = q.front();  q.pop();  int x = p.first, y = p.second;  COUNT++;  // Go to the adjacent cells  for (int i = 0; i < 4; i++) {  int newX = x + dx[i];  int newY = y + dy[i];  if (is_valid(newX, newY, matrix)) {  q.push({ newX, newY });  visited[newX][newY] = true;  }  }  }  mp[COUNT]++;  }  }  } } // Drivers Code int main() {  // Given input array of 1s and 0s  int matrix[n][m]  = { { 1, 1, 1, 1, 1, 1 }, { 1, 1, 0, 0, 0, 0 },   { 0, 0, 0, 1, 1, 1 }, { 0, 0, 0, 1, 1, 1 },   { 0, 0, 1, 0, 0, 0 }, { 1, 0, 0, 0, 0, 0 } };  // queries array  int queries[] = { 6, 1, 8, 2 };  // sizeof queries array  int N = sizeof(queries) / sizeof(queries[0]);  // Initialize all cells unvisited  memset(visited, false, sizeof visited);  // Count the frequency of each connected component  findComponentSize(matrix);  // Iterate over the given queries array and  // And answer the queries  for (int i = 0; i < N; i++)  cout << mp[queries[i]] << " ";  return 0; }

Java

// Java implementation for the above approach import java.util.*; class GFG{  static class pair  {   int first, second;   public pair(int first, int second)   {   this.first = first;   this.second = second;   }   }  static int n = 6; static int m = 6; static int dx[] = { 0, 1, -1, 0 }; static int dy[] = { 1, 0, 0, -1 }; // stores information about which cell // are already visited in a particular BFS static int [][]visited = new int[n][m]; // Stores the final result grid static int[][] result = new int[n][m]; // Stores the count of cells in // the largest connected component static int COUNT; // Function checks if a cell is valid, i.e. // it is inside the grid and equal to 1 static boolean is_valid(int x, int y, int matrix[][]) {  if (x < n && y < m && x >= 0 && y >= 0) {  if (visited[x][y] == 0  && matrix[x][y] == 1)  return true;  else  return false;  }  else  return false; } // Map to count the frequency of // each connected component static HashMap<Integer,Integer> mp = new HashMap<Integer,Integer>(); // function to calculate the // largest connected component static void findComponentSize(int matrix[][]) {  // Iterate over every cell  for (int i = 0; i < n; i++) {  for (int j = 0; j < m; j++) {  if (visited[i][j]==0 && matrix[i][j] == 1) {  COUNT = 0;  // Stores the indices of the matrix cells  Queue<pair > q = new LinkedList<>();  // Mark the starting cell as visited  // and push it into the queue  q.add(new pair( i, j ));  visited[i][j] = 1;  // Iterate while the queue  // is not empty  while (!q.isEmpty()) {  pair p = q.peek();  q.remove();  int x = p.first, y = p.second;  COUNT++;  // Go to the adjacent cells  for (int k = 0; k < 4; k++) {  int newX = x + dx[k];  int newY = y + dy[k];  if (is_valid(newX, newY, matrix)) {  q.add(new pair(newX, newY ));  visited[newX][newY] = 1;  }  }  }  if(mp.containsKey(COUNT)){  mp.put(COUNT, mp.get(COUNT)+1);  }  else{  mp.put(COUNT, 1);  }  }  }  } } // Drivers Code public static void main(String[] args) {  // Given input array of 1s and 0s  int matrix[][]  = { { 1, 1, 1, 1, 1, 1 }, { 1, 1, 0, 0, 0, 0 },   { 0, 0, 0, 1, 1, 1 }, { 0, 0, 0, 1, 1, 1 },   { 0, 0, 1, 0, 0, 0 }, { 1, 0, 0, 0, 0, 0 } };  // queries array  int queries[] = { 6, 1, 8, 2 };  // sizeof queries array  int N = queries.length;    // Count the frequency of each connected component  findComponentSize(matrix);  // Iterate over the given queries array and  // And answer the queries  for (int i = 0; i < N; i++)  System.out.print((mp.get(queries[i])!=null?mp.get(queries[i]):0)+ " "); } } // This code is contributed by 29AjayKumar

Python3

# Python 3 implementation for the above approach n = 6 m = 6 dx = [0, 1, -1, 0] dy = [1, 0, 0, -1] # stores information about which cell # are already visited in a particular BFS visited = [[False for i in range(m)] for j in range(n)] # Stores the final result grid result = [[0 for i in range(m)] for j in range(n)] # Stores the count of cells in # the largest connected component COUNT = 0 # Function checks if a cell is valid, i.e. # it is inside the grid and equal to 1 def is_valid(x, y, matrix): if (x < n and y < m and x >= 0 and y >= 0): if (visited[x][y] == False and matrix[x][y] == 1): return True else: return False else: return False # Map to count the frequency of # each connected component mp = {} # function to calculate the # largest connected component def findComponentSize(matrix): # Iterate over every cell for i in range(n): for j in range(m): if(visited[i][j]== False and matrix[i][j] == 1): COUNT = 0 # Stores the indices of the matrix cells q = [] # Mark the starting cell as visited # and push it into the queue q.append([i, j]) visited[i][j] = True # Iterate while the queue # is not empty while (len(q)!=0): p = q[0] q = q[1:] x = p[0] y = p[1] COUNT += 1 # Go to the adjacent cells for i in range(4): newX = x + dx[i] newY = y + dy[i] if (is_valid(newX, newY, matrix)): q.append([newX, newY]) visited[newX][newY] = True if COUNT in mp: mp[COUNT] += 1 else: mp[COUNT] = 1 # Drivers Code if __name__ == '__main__': # Given input array of 1s and 0s matrix = [[1, 1, 1, 1, 1, 1], [1, 1, 0, 0, 0, 0], [0, 0, 0, 1, 1, 1], [0, 0, 0, 1, 1, 1], [0, 0, 1, 0, 0, 0], [1, 0, 0, 0, 0, 0]] # queries array queries = [6, 1, 8, 2] # sizeof queries array N = len(queries) # Count the frequency of each connected component findComponentSize(matrix) # Iterate over the given queries array and # And answer the queries for i in range(N): if queries[i] in mp: print(mp[queries[i]],end = " ") else: print(0,end = " ") # This code is contributed by SURENDRA_GANGWAR.

// C# implementation for the above approach using System; using System.Collections.Generic; public class GFG{  class pair  {   public int first, second;   public pair(int first, int second)   {   this.first = first;   this.second = second;   }   }  static int n = 6; static int m = 6; static int []dx = { 0, 1, -1, 0 }; static int []dy = { 1, 0, 0, -1 }; // stores information about which cell // are already visited in a particular BFS static int [,]visited = new int[n,m]; // Stores the count of cells in // the largest connected component static int COUNT; // Function checks if a cell is valid, i.e. // it is inside the grid and equal to 1 static bool is_valid(int x, int y, int [,]matrix) {  if (x < n && y < m && x >= 0 && y >= 0) {  if (visited[x,y] == 0  && matrix[x,y] == 1)  return true;  else  return false;  }  else  return false; } // Map to count the frequency of // each connected component static Dictionary<int,int> mp = new Dictionary<int,int>(); // function to calculate the // largest connected component static void findComponentSize(int [,]matrix) {  // Iterate over every cell  for (int i = 0; i < n; i++) {  for (int j = 0; j < m; j++) {  if (visited[i,j]==0 && matrix[i,j] == 1) {  COUNT = 0;  // Stores the indices of the matrix cells  List<pair> q = new List<pair>();  // Mark the starting cell as visited  // and push it into the queue  q.Add(new pair( i, j ));  visited[i,j] = 1;  // Iterate while the queue  // is not empty  while (q.Count>0) {  pair p = q[0];  q.RemoveAt();  int x = p.first, y = p.second;  COUNT++;  // Go to the adjacent cells  for (int k = 0; k < 4; k++) {  int newX = x + dx[k];  int newY = y + dy[k];  if (is_valid(newX, newY, matrix)) {  q.Add(new pair(newX, newY ));  visited[newX,newY] = 1;  }  }  }  if(mp.ContainsKey(COUNT)){  mp[COUNT] += 1;  }  else{  mp.Add(COUNT, 1);  }  }  }  } } // Drivers Code public static void Main() {  // Given input array of 1s and 0s  int [,]matrix  = new int[,]{ { 1, 1, 1, 1, 1, 1 }, { 1, 1, 0, 0, 0, 0 },   { 0, 0, 0, 1, 1, 1 }, { 0, 0, 0, 1, 1, 1 },   { 0, 0, 1, 0, 0, 0 }, { 1, 0, 0, 0, 0, 0 } };  // queries array  int []queries = { 6, 1, 8, 2 };  // sizeof queries array  int N = queries.Length;  for(int i=0;i<n;i++){  for(int j=0;j<m;j++){  visited[i,j] = 0;  }  }    // Count the frequency of each connected component  findComponentSize(matrix);  // Iterate over the given queries array and  // And answer the queries  for (int i = 0; i < N; i++)  if(mp.ContainsKey(queries[i])!=false)  Console.Write(mp[queries[i]] + " "); } } // This code is contributed by 29AjayKumar

JavaScript

// JavaScript implementation for the above approach const n = 6; const m = 6; const dx = [0, 1, -1, 0]; const dy = [1, 0, 0, -1]; // stores information about which cell // are already visited in a particular BFS let visited = []; for (let i = 0; i < n; i++) {  visited.push(new Array(m).fill(0)); } // Stores the final result grid let result = []; for (let i = 0; i < n; i++) {  result.push(new Array(m).fill(0)); } // Stores the count of cells in // the largest connected component let COUNT = 0; // Function checks if a cell is valid, i.e. // it is inside the grid and equal to 1 const is_valid = (x, y, matrix) => {  if (x < n && y < m && x >= 0 && y >= 0) {  if (visited[x][y] === 0 && matrix[x][y] === 1) {  return true;  } else {  return false;  }  } else {  return false;  } }; // Map to count the frequency of // each connected component let mp = new Map(); // function to calculate the // largest connected component const findComponentSize = (matrix) => {  // Iterate over every cell  for (let i = 0; i < n; i++) {  for (let j = 0; j < m; j++) {  if (visited[i][j] === 0 && matrix[i][j] === 1) {  COUNT = 0;  // Stores the indices of the matrix cells  let q = [];  // Mark the starting cell as visited  // and push it into the queue  q.push([i, j]);  visited[i][j] = 1;  // Iterate while the queue  // is not empty  while (q.length > 0) {  let p = q.shift();  let x = p[0],  y = p[1];  COUNT++;  // Go to the adjacent cells  for (let k = 0; k < 4; k++) {  let newX = x + dx[k];  let newY = y + dy[k];  if (is_valid(newX, newY, matrix)) {  q.push([newX, newY]);  visited[newX][newY] = 1;  }  }  }  if (mp.has(COUNT)) {  mp.set(COUNT, mp.get(COUNT) + 1);  } else {  mp.set(COUNT, 1);  }  }  }  } }; // Driver code // Given input array of 1s and 0s const matrix = [  [1, 1, 1, 1, 1, 1],  [1, 1, 0, 0, 0, 0],  [0, 0, 0, 1, 1, 1],  [0, 0, 0, 1, 1, 1],  [0, 0, 1, 0, 0, 0],  [1, 0, 0, 0, 0, 0] ] // queries array let queries = [6, 1, 8, 2] // sizeof queries array let N = queries.length // Count the frequency of each connected component findComponentSize(matrix) // Iterate over the given queries array and // And answer the queries for (var i = 0; i < N; i++) {  if (mp.has(queries[i]))  process.stdout.write(mp.get(queries[i]) + " ")  else  process.stdout.write("0 ") }