Given a boolean matrix mat[][] consisting of N rows and M columns, initially filled with 0‘s(empty cells), an integer K and queries Q[][] of the type {X, Y}, the task is to replace mat[X][Y] = 1(non-empty cells) and count the number of connected non-empty cells from the given matrix.
Examples:
Input: N = 3, M = 3, K = 4, Q[][] = {{0, 0}, {1, 1}, {1, 0}, {1, 2}}
Output: 1 2 1 1
Explanation:
Initially, mat[][] = {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}}
Query 1: mat[][] = {{1, 0, 0}, {0, 0, 0}, {0, 0, 0}}, Count = 1
Query 1: mat[][] = {{1, 0, 0}, {0, 1, 0}, {0, 0, 0}}, Count = 2
Query 1: mat[][] = {{1, 0, 0}, {1, 1, 0}, {0, 0, 0}}, Count = 1
Query 1: mat[][] = {{1, 0, 0}, {1, 1, 1}, {0, 0, 0}}, Count = 1
Input: N = 2, M = 2, K = 2, Q[][] = {{0, 0}, {0, 1}}
Output : 1 1
Approach:
The problem can be solved using Disjoint Set Data Structure. Follow the steps below to solve the problem:
- Since, initially, there are no 1‘s in the matrix, count = 0.
- Transform the two-dimension problem into the classic Union-find, by performing a linear mapping index = X * M + Y, where M is the column length.
- After setting an index in each query, increment count.
- If a non-empty cell is present in any of the 4 adjacent cells:
- Perform Union operation for the current index and adjacent cell(connecting two Sets).
- Decrement count as two Sets are connected.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Count of connected cellsint ctr = 0;// Function to return the representative// of the Set to which x belongsint find(vector<int>& parent, int x){ // If x is parent of itself if (parent[x] == x) // x is representative // of the Set return x; // Otherwise parent[x] = find(parent, parent[x]); // Path Compression return parent[x];}// Unites the set that includes// x and the set that includes yvoid setUnion(vector<int>& parent, vector<int>& rank, int x, int y){ // Find the representatives(or the // root nodes) for x an y int parentx = find(parent, x); int parenty = find(parent, y); // If both are in the same set if (parenty == parentx) return; // Decrement count ctr--; // If x's rank is less than y's rank if (rank[parentx] < rank[parenty]) { parent[parentx] = parenty; } // Otherwise else if (rank[parentx] > rank[parenty]) { parent[parenty] = parentx; } else { // Then move x under y (doesn't matter // which one goes where) parent[parentx] = parenty; // And increment the result tree's // rank by 1 rank[parenty]++; }}// Function to count the number of// connected cells in the matrixvector<int> solve(int n, int m, vector<pair<int, int> >& query){ // Store result for queries vector<int> result(query.size()); // Store representative of // each element vector<int> parent(n * m); // Initially, all elements // are in their own set for (int i = 0; i < n * m; i++) parent[i] = i; // Stores the rank(depth) of each node vector<int> rank(n * m, 1); vector<bool> grid(n * m, 0); for (int i = 0; i < query.size(); i++) { int x = query[i].first; int y = query[i].second; // If the grid[x*m + y] is already // set, store the result if (grid[m * x + y] == 1) { result[i] = ctr; continue; } // Set grid[x*m + y] to 1 grid[m * x + y] = 1; // Increment count. ctr++; // Check for all adjacent cells // to do a Union with neighbour's // set if neighbour is also 1 if (x > 0 and grid[m * (x - 1) + y] == 1) setUnion(parent, rank, m * x + y, m * (x - 1) + y); if (y > 0 and grid[m * (x) + y - 1] == 1) setUnion(parent, rank, m * x + y, m * (x) + y - 1); if (x < n - 1 and grid[m * (x + 1) + y] == 1) setUnion(parent, rank, m * x + y, m * (x + 1) + y); if (y < m - 1 and grid[m * (x) + y + 1] == 1) setUnion(parent, rank, m * x + y, m * (x) + y + 1); // Store result. result[i] = ctr; } return result;}// Driver Codeint main(){ int N = 3, M = 3, K = 4; vector<pair<int, int> > query = { { 0, 0 }, { 1, 1 }, { 1, 0 }, { 1, 2 } }; vector<int> result = solve(N, M, query); for (int i = 0; i < K; i++) cout << result[i] << " ";} |
Java
// Java program to implement// the above approachimport java.util.*;class GFG{// Count of connected cellsstatic int ctr = 0;// Function to return the representative// of the Set to which x belongsstatic int find(int []parent, int x){ // If x is parent of itself if (parent[x] == x) // x is representative // of the Set return x; // Otherwise parent[x] = find(parent, parent[x]); // Path Compression return parent[x];}// Unites the set that includes// x and the set that includes ystatic void setUnion(int[] parent, int[] rank, int x, int y){ // Find the representatives(or the // root nodes) for x an y int parentx = find(parent, x); int parenty = find(parent, y); // If both are in the same set if (parenty == parentx) return; // Decrement count ctr--; // If x's rank is less than y's rank if (rank[parentx] < rank[parenty]) { parent[parentx] = parenty; } // Otherwise else if (rank[parentx] > rank[parenty]) { parent[parenty] = parentx; } else { // Then move x under y (doesn't matter // which one goes where) parent[parentx] = parenty; // And increment the result tree's // rank by 1 rank[parenty]++; }}// Function to count the number of// connected cells in the matrixstatic int [] solve(int n, int m, int [][]query){ // Store result for queries int []result = new int[query.length]; // Store representative of // each element int []parent = new int[n * m]; // Initially, all elements // are in their own set for(int i = 0; i < n * m; i++) parent[i] = i; // Stores the rank(depth) of each node int []rank = new int[n * m]; Arrays.fill(rank, 1); boolean []grid = new boolean[n * m]; for(int i = 0; i < query.length; i++) { int x = query[i][0]; int y = query[i][1]; // If the grid[x*m + y] is already // set, store the result if (grid[m * x + y] == true) { result[i] = ctr; continue; } // Set grid[x*m + y] to 1 grid[m * x + y] = true; // Increment count. ctr++; // Check for all adjacent cells // to do a Union with neighbour's // set if neighbour is also 1 if (x > 0 && grid[m * (x - 1) + y] == true) setUnion(parent, rank, m * x + y, m * (x - 1) + y); if (y > 0 && grid[m * (x) + y - 1] == true) setUnion(parent, rank, m * x + y, m * (x) + y - 1); if (x < n - 1 && grid[m * (x + 1) + y] == true) setUnion(parent, rank, m * x + y, m * (x + 1) + y); if (y < m - 1 && grid[m * (x) + y + 1] == true) setUnion(parent, rank, m * x + y, m * (x) + y + 1); // Store result. result[i] = ctr; } return result;}// Driver Codepublic static void main(String[] args){ int N = 3, M = 3, K = 4; int [][]query = { { 0, 0 }, { 1, 1 }, { 1, 0 }, { 1, 2 } }; int[] result = solve(N, M, query); for(int i = 0; i < K; i++) System.out.print(result[i] + " ");}}// This code is contributed by Amit Katiyar |
Python3
# Python 3 program to implement# the above approach# Count of connected cellsctr = 0# Function to return the # representative of the Set # to which x belongsdef find(parent, x): # If x is parent of itself if (parent[x] == x): # x is representative # of the Set return x # Otherwise parent[x] = find(parent, parent[x]) # Path Compression return parent[x]# Unites the set that # includes x and the # set that includes ydef setUnion(parent, rank, x, y): global ctr # Find the representatives # (or the root nodes) for x an y parentx = find(parent, x) parenty = find(parent, y) # If both are in the same set if (parenty == parentx): return # Decrement count ctr -= 1 # If x's rank is less than y's rank if (rank[parentx] < rank[parenty]): parent[parentx] = parenty # Otherwise elif (rank[parentx] > rank[parenty]): parent[parenty] = parentx else: # Then move x under y # (doesn't matter which # one goes where) parent[parentx] = parenty # And increment the result # tree's rank by 1 rank[parenty] += 1 # Function to count the number of# connected cells in the matrixdef solve(n, m, query): global ctr # Store result for queries result = [0] * len(query) # Store representative of # each element parent = [0] * (n * m) # Initially, all elements # are in their own set for i in range (n * m): parent[i] = i # Stores the rank(depth) # of each node rank = [1] * (n * m) grid = [0] * (n * m) for i in range (len( query)): x = query[i][0] y = query[i][1] # If the grid[x*m + y] is already # set, store the result if (grid[m * x + y] == 1): result[i] = ctr continue # Set grid[x*m + y] to 1 grid[m * x + y] = 1 # Increment count. ctr += 1 # Check for all adjacent cells # to do a Union with neighbour's # set if neighbour is also 1 if (x > 0 and grid[m * (x - 1) + y] == 1): setUnion(parent, rank, m * x + y, m * (x - 1) + y) if (y > 0 and grid[m * (x) + y - 1] == 1): setUnion(parent, rank, m * x + y, m * (x) + y - 1) if (x < n - 1 and grid[m * (x + 1) + y] == 1): setUnion(parent, rank, m * x + y, m * (x + 1) + y) if (y < m - 1 and grid[m * (x) + y + 1] == 1): setUnion(parent, rank, m * x + y, m * (x) + y + 1) # Store result. result[i] = ctr return result# Driver Codeif __name__ == "__main__": N = 3 M = 3 K = 4 query = [[0, 0], [1, 1], [1, 0], [1, 2]] result = solve(N, M, query) for i in range (K): print (result[i], end = " ") # This code is contributed by Chitranayal |
C#
// C# program to implement// the above approachusing System;class GFG{// Count of connected cellsstatic int ctr = 0;// Function to return the representative// of the Set to which x belongsstatic int find(int []parent, int x){ // If x is parent of itself if (parent[x] == x) // x is representative // of the Set return x; // Otherwise parent[x] = find(parent, parent[x]); // Path Compression return parent[x];}// Unites the set that includes// x and the set that includes ystatic void setUnion(int[] parent, int[] rank, int x, int y){ // Find the representatives(or the // root nodes) for x an y int parentx = find(parent, x); int parenty = find(parent, y); // If both are in the same set if (parenty == parentx) return; // Decrement count ctr--; // If x's rank is less than y's rank if (rank[parentx] < rank[parenty]) { parent[parentx] = parenty; } // Otherwise else if (rank[parentx] > rank[parenty]) { parent[parenty] = parentx; } else { // Then move x under y (doesn't matter // which one goes where) parent[parentx] = parenty; // And increment the result tree's // rank by 1 rank[parenty]++; }}// Function to count the number of// connected cells in the matrixstatic int [] solve(int n, int m, int [,]query){ // Store result for queries int []result = new int[query.Length]; // Store representative of // each element int []parent = new int[n * m]; // Initially, all elements // are in their own set for(int i = 0; i < n * m; i++) parent[i] = i; // Stores the rank(depth) of each node int []rank = new int[n * m]; for(int i = 0; i < rank.Length; i++) rank[i] = 1; bool []grid = new bool[n * m]; for(int i = 0; i < query.GetLength(0); i++) { int x = query[i, 0]; int y = query[i, 1]; // If the grid[x*m + y] is already // set, store the result if (grid[m * x + y] == true) { result[i] = ctr; continue; } // Set grid[x*m + y] to 1 grid[m * x + y] = true; // Increment count. ctr++; // Check for all adjacent cells // to do a Union with neighbour's // set if neighbour is also 1 if (x > 0 && grid[m * (x - 1) + y] == true) setUnion(parent, rank, m * x + y, m * (x - 1) + y); if (y > 0 && grid[m * (x) + y - 1] == true) setUnion(parent, rank, m * x + y, m * (x) + y - 1); if (x < n - 1 && grid[m * (x + 1) + y] == true) setUnion(parent, rank, m * x + y, m * (x + 1) + y); if (y < m - 1 && grid[m * (x) + y + 1] == true) setUnion(parent, rank, m * x + y, m * (x) + y + 1); // Store result. result[i] = ctr; } return result;}// Driver Codepublic static void Main(String[] args){ int N = 3, M = 3, K = 4; int [,]query = {{ 0, 0 }, { 1, 1 }, { 1, 0 }, { 1, 2 }}; int[] result = solve(N, M, query); for(int i = 0; i < K; i++) Console.Write(result[i] + " ");}}// This code is contributed by sapnasingh4991 |
Javascript
<script>// Javascript program to implement// the above approach// Count of connected cellslet ctr = 0;// Function to return the representative// of the Set to which x belongsfunction find(parent,x){ // If x is parent of itself if (parent[x] == x) // x is representative // of the Set return x; // Otherwise parent[x] = find(parent, parent[x]); // Path Compression return parent[x];}// Unites the set that includes// x and the set that includes yfunction setUnion(parent,rank,x,y){ // Find the representatives(or the // root nodes) for x an y let parentx = find(parent, x); let parenty = find(parent, y); // If both are in the same set if (parenty == parentx) return; // Decrement count ctr--; // If x's rank is less than y's rank if (rank[parentx] < rank[parenty]) { parent[parentx] = parenty; } // Otherwise else if (rank[parentx] > rank[parenty]) { parent[parenty] = parentx; } else { // Then move x under y (doesn't matter // which one goes where) parent[parentx] = parenty; // And increment the result tree's // rank by 1 rank[parenty]++; }}// Function to count the number of// connected cells in the matrixfunction solve(n,m,query){ // Store result for queries let result = new Array(query.length); // Store representative of // each element let parent = new Array(n * m); // Initially, all elements // are in their own set for(let i = 0; i < n * m; i++) parent[i] = i; // Stores the rank(depth) of each node let rank = new Array(n * m); let grid = new Array(n * m); for(let i=0;i<(n*m);i++) { rank[i]=0; grid[i]=false; } for(let i = 0; i < query.length; i++) { let x = query[i][0]; let y = query[i][1]; // If the grid[x*m + y] is already // set, store the result if (grid[m * x + y] == true) { result[i] = ctr; continue; } // Set grid[x*m + y] to 1 grid[m * x + y] = true; // Increment count. ctr++; // Check for all adjacent cells // to do a Union with neighbour's // set if neighbour is also 1 if (x > 0 && grid[m * (x - 1) + y] == true) setUnion(parent, rank, m * x + y, m * (x - 1) + y); if (y > 0 && grid[m * (x) + y - 1] == true) setUnion(parent, rank, m * x + y, m * (x) + y - 1); if (x < n - 1 && grid[m * (x + 1) + y] == true) setUnion(parent, rank, m * x + y, m * (x + 1) + y); if (y < m - 1 && grid[m * (x) + y + 1] == true) setUnion(parent, rank, m * x + y, m * (x) + y + 1); // Store result. result[i] = ctr; } return result;}// Driver Codelet N = 3, M = 3, K = 4;let query = [[ 0, 0 ], [ 1, 1 ], [ 1, 0 ], [ 1, 2 ]]; let result = solve(N, M, query);for(let i = 0; i < K; i++) document.write(result[i] + " ");// This code is contributed by avanitrachhadiya2155</script> |
Output:
1 2 1 1
Time Complexity: O(N * M * sizeof(Q))
Auxiliary Space: 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!
