Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Approach
4.
Code in C++
4.1.
Output
4.2.
Time Complexity 
4.3.
Space Complexity 
5.
Frequently Asked Questions
6.
Key Takeaways
Last Updated: Mar 27, 2024

Find the number of connected grids of a given size in a 2D-Matrix

Author Gaurish Anand
0 upvote
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction

Before beginning with this question, let's recap what a Depth First Traversal means. 

                    

Source

DFS Algorithm is an algorithm used to traverse a graph or a tree. This algorithm is similar to a DFS traversal in a tree. But the main difference is in graphs, you can have cycles, but in trees, we can't have them. 

So to do a DFS traversal in a graph, we begin from any random node and travel down each branch as far as feasible before returning to the current node. 

Since here we can have cycles; therefore we need to maintain a visited array too to avoid an infinite loop. For further reference, you can go through this article.

Example: Depth First Traversal for the above graph is: 1 2 3 4 5 6 

Problem Statement

You are given a binary matrix of size n*m and an array of Q queries. Your task is to find the number of connected components of size q for each query.

Note: Connected components are cells with a value of 1 and share at least 1 common side. For example, the connected components in the matrix below are: 

Depth First Traversal in a 2D Matrix will be similar to a normal DFS. The only difference here is of the neighbors for each cell.

For example: Let's find the neighbors for the cell [1,1] in the above matrix. 

Neighbors for this cell will be the adjacent cells with a value of 1. Therefore neighbours for [1,1] will be [0,1] and [1,0]. 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach

Do a DFS traversal on the matrix, find the number of cells in each component, and store their frequency in a hashmap. You can go through this article for further reference to a DFS Traversal in a 2D Matrix.

Code in C++

#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;

// This function will return the number of connected cells around the starting [i,j]
int dfs(vector<vector<int> >& visited,vector<vector<int>>& grid,int i,int j){
	if(i<0 || j<0 || i>=grid.size() || j>=grid[i].size()){
		return 0; // If we go out of the matrix, then no connected cell
    }

    // If the cell has been already visited or if the cell is marked as 0, then don't
    // need to visit this cell.
    if(visited[i][j]==true || grid[i][j]==0){
        return 0;
    }

    visited[i][j]=true;

    // Travel on the connected cells
    int connectedCells = 1;
    connectedCells += dfs(visited,grid,i+1,j);
    connectedCells += dfs(visited,grid,i-1,j);
    connectedCells += dfs(visited,grid,i,j+1);
    connectedCells += dfs(visited,grid,i,j-1);
    return connectedCells;
}

// This function will return the frequency of each size of a connected grid present in the matrix
unordered_map<int,int> findFrequency(vector<vector<int>>& grid) {
    unordered_map<int,int> ans;

    // First making a visited array to maintain the cells already visited during the DFS call.
    vector<vector<int> > visited(
    	grid.size(),
    	vector<int>(grid[0].size(),false)
    );

    for(int i=0;i<grid.size();i++){
        for(int j=0;j<grid[i].size();j++){
            if(visited[i][j]==false && grid[i][j]==1){
            	// Count the number of cells in this connected 
            	// grid and update its size in the hashmap
                int count = dfs(visited,grid,i,j);
                ans[count]++;
            }
        }
    }

    return ans;
}

int main(){
	vector<vector<int> > grid{
		{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},
	};

	vector<int> queries{6 , 1 , 8, 2};

	unordered_map<int,int> frequencyCount = findFrequency(grid);
	for(int i=0;i<queries.size();i++){
		cout<<frequencyCount[queries[i]]<<endl;
	}
}

Output

1
2
1
0

Time Complexity 

Since time complexity will be O(1) for each query, time complexity = O(Q) where Q = number of queries. The time complexity for precomputing each connected grid's size will be O(n*m), where n is the number of rows and m is the number of columns in the matrix.

Space Complexity 

We are making a hashmap that will store the frequency of the number of times a particular size of the connected component occurs. Since the size of the connected component can vary from 1 to n*m, the space complexity due to this hashmap will be O(n*m), where n is the number of rows and m is the number of columns in the matrix.

Frequently Asked Questions

  1. What is the difference between a tree and a graph?
    Trees and graphs are different since there can never be loops in a tree, but we can have loops in a graph. Also, all the nodes in a tree are always connected, but that is not true for a graph.
     
  2. What is the difference between a DFS Traversal and a BFS Traversal?
    In a DFS traversal of a graph, we begin from any random node and travel down each branch as feasible before returning to the current node. In contrast, in a BFS traversal, we visit each node at the current level before visiting their children nodes. 
    DFS Traversal is performed using a stack, whereas a BFS Traversal is performed using a queue.
     
  3. Are there more Data Structures and Algorithms problems in Coding Ninjas Studio?
    Yes, Coding Ninjas Studio is a platform that provides both practice coding questions and commonly asked interview questions. The more we'll practice, the better our chances are of getting into a dream company of ours.

Key Takeaways

In this article, we learned to do a DFS traversal on a 2D Matrix and calculate the size of the connected components.

Since graphs are frequently asked in interviews, we recommend you practice more problems based on graphs on Coding Ninjas Studio. 

Check out this problem - Matrix Median

Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more? Attempt our Online Mock Test Series on Coding Ninjas Studio now!

Previous article
Maximum element in the connected component of the given node for Q queries
Next article
Minimum nodes to be colored in a graph such that every node has a colored neighbor
Live masterclass