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

0 0 11 minutes read

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#

// 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 ")
}

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 zambiatek!