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 BFSint visited[n][m];// Stores the count of cells in// the largest connected componentint COUNT;// Function checks if a cell is valid, i.e.// it is inside the grid and equal to 1bool 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 componentmap<int, int> mp;// function to calculate the// largest connected componentvoid 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 Codeint 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 approachimport 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 BFSstatic int [][]visited = new int[n][m];// Stores the final result gridstatic int[][] result = new int[n][m];// Stores the count of cells in// the largest connected componentstatic int COUNT;// Function checks if a cell is valid, i.e.// it is inside the grid and equal to 1static 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 componentstatic HashMap<Integer,Integer> mp = new HashMap<Integer,Integer>();// function to calculate the// largest connected componentstatic 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 Codepublic 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 approachn = 6m = 6dx = [0, 1, -1, 0]dy = [1, 0, 0, -1]# stores information about which cell# are already visited in a particular BFSvisited = [[False for i in range(m)] for j in range(n)]# Stores the final result gridresult = [[0 for i in range(m)] for j in range(n)]# Stores the count of cells in# the largest connected componentCOUNT = 0# Function checks if a cell is valid, i.e.# it is inside the grid and equal to 1def 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 componentmp = {}# function to calculate the# largest connected componentdef 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 Codeif __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#
// C# implementation for the above approachusing 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 BFSstatic int [,]visited = new int[n,m];// Stores the count of cells in// the largest connected componentstatic int COUNT;// Function checks if a cell is valid, i.e.// it is inside the grid and equal to 1static 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 componentstatic Dictionary<int,int> mp = new Dictionary<int,int>();// function to calculate the// largest connected componentstatic 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 Codepublic 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 approachconst 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 BFSlet visited = [];for (let i = 0; i < n; i++) { visited.push(new Array(m).fill(0));}// Stores the final result gridlet result = [];for (let i = 0; i < n; i++) { result.push(new Array(m).fill(0));}// Stores the count of cells in// the largest connected componentlet COUNT = 0;// Function checks if a cell is valid, i.e.// it is inside the grid and equal to 1const 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 componentlet mp = new Map();// function to calculate the// largest connected componentconst 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 0sconst 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 arraylet queries = [6, 1, 8, 2]// sizeof queries arraylet N = queries.length// Count the frequency of each connected componentfindComponentSize(matrix)// Iterate over the given queries array and// And answer the queriesfor (var i = 0; i < N; i++) { if (mp.has(queries[i])) process.stdout.write(mp.get(queries[i]) + " ") else process.stdout.write("0 ")} |
Output:
1 2 1 0
Time Complexity: O(n*m)
Space Complexity: O(n*m)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
