Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Problem Statement
2.
Constraints
3.
Sample Test Cases
4.
Approach
5.
Code
6.
Example
7.
Time Complexity
8.
Space Complexity
9.
FAQs
10.
Key Takeaways
Last Updated: Mar 27, 2024

Find Regions with Most Common Region Size in a Given Boolean Matrix

Problem Statement

 

You are given a boolean matrix A[][] of size N * M where '1' denotes land, and '0' denotes water. A set of connected '1's is called an island. Two land cells are said to be connected if they are horizontally, vertically, or diagonally adjacent to each other. You need to find the coordinates of the top left corners of all the islands with the most common island size. The island size is the total number of cells in it.

Constraints

 

1 <= N, M <= 1000

 

Sample Test Cases

 

Input 1: 4 5
         1 1 0 0 1
         1 1 0 0 0
         0 0 0 1 1
         0 0 0 1 1

Output 1: 2
          0 0
          2 3

Explanation: There are two islands with length 3 and one with length 1. So four is the most common island size, and the top left corner coordinates of islands are (0, 0) and (2, 3).


Input 1: 3 3
         1 1 0 0 1
         1 1 0 0 0
         0 0 0 1 1
         1 0 0 1 1

Output 1: 2
          0 4
          3 1

Explanation: There are two islands with length 3 and two with length 1. So both are the most common island sizes. So we can output the coordinates of any one.

Approach

 

We can find the number of the island (number of connected components) using a depth-first search. Also, we can calculate the size of each island by keeping the count of all the valid cells visited during the DFS traversal.

So we can solve this problem by storing the coordinates of the top-left cell with the size of the island in a hashmap. 

Steps to solve:

  • Initialize a hashmap to hash integer with the vector of pairs. The integer represents the size, and the vector stores the top-left coordinate of all the islands of that size. 
  • Maintain a visited array to keep note of all cells that have already been visited.
  • Traverse the given matrix row-wise, and if the current cell (r, c) is land (A[r][c] == 1) and is not visited (visited[r][c] == 0), initiate DFS traversal from this cell and keeps the count of all cells visited during traversal.
  • If we are at coordinate (r, c) and A[r][c] == 1 and visited[r][c] == 0, then all the coordinates (x, y) such that x < r or y < c are already visited (if it was a land). So if we initiate the DFS traversal from (r, c), then we will not visit such cells during traversal. Thus we can claim the cell (r, c) is the coordinate of the top-left cell of an island.
  • After traversal, store the size of the island and coordinate of the top-left cell in the hashmap.
  • Iterate over the hashmap to find the size of the most common region and then print all the coordinates mapped with it. 

Code

 

#include <bits/stdc++.h>
using namespace std;
const int mxRow = 1000, mxCol = 1000;

//rows, column
int N, M;
//input matrix 
int A[mxRow][mxCol];
//boolean array to mark visited cells
//all the cells are initially unvisited
bool visited[mxRow][mxCol];

//displacement vectors (gives the coordinate of all the eight neighbours)
int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};

//function to check, whether the given cell can be visited or not   
bool isValid(int x, int y){
   //out of bound
   if(x < 0 || y < 0 || x >= N | y >= M)
       return false;
   //water or already visited
   if(visited[x][y] || !A[x][y])
       return false;
   return true;
}
//function to do depth first search for a 2D grid
void dfs(int r, int c, int &cnt){
   //mark the cell as visited
   visited[r][c] = true;
   //visit the neigbours 
   for(int i = 0; i < 8; i++){
       if(isValid(r + dx[i], c + dy[i])){
           //if the neigbour is valid increment the length of region by one
           cnt++;
           dfs(r + dx[i], c + dy[i], cnt);
       }
   }
}
int main(){
   cin >> N >> M; //rows, column
   for(int i = 0; i < N; i++){
       for(int j = 0; j < M; j++){
           cin >> A[i][j];
       }
   }
   //map to store the size and coordinate of top left cell
   unordered_map <int, vector <pair<int, int>>> mp;
   for(int i = 0; i < N; ++i){
       for(int j = 0; j < M; j++){
           if(!A[i][j] || visited[i][j])
               continue;
           //if the current cell is land (i.e, A[i][j] == 1) 
           //and is not visited (i.e, visited[i][j] == 0)
           int cnt = 1; //initialize the region size by 1
           
           //dfs call
           dfs(i, j, cnt);
           //(i, j) is the coordinates of top left cell
           mp[cnt].push_back({i, j});
       }
   }
   int most_common_region = 0; //store the number of most common region
   int size = 0;  //size of most common region
   for(auto u : mp){
       if(mp[u.first].size() > most_common_region){
           most_common_region = mp[u.first].size();
           size = u.first;
       }
   }

   //traverse the vector mapped with size of most common region
   //to print the coordinates of top left cells
   for(auto u : mp[size]){
       cout << u.first << " " << u.second << "\n";
   }
   return 0;
}

Example

 

 

Time Complexity

 

The overall time complexity is O(N * M).

Space Complexity

 

We need an extra 2D boolean array of size N x M to mark the visited cells. So the overall space complexity is O(N * M).

Check this out, Fibonacci Series in Python

FAQs

  1. What is DFS?
    DFS stands for depth-first search. It is a graph theory algorithm for recursively traversing or searching graphs and trees. 
     
  2. What is the time complexity of DFS?
    The time complexity of DFS is O(V + E), where V is vertices and E is edges.
     
  3. What is the time complexity of unordered_map?  
    The average case time complexity of an unordered map is O(1).

 

Key Takeaways

 

In this article, we solved a graph theory problem. Having a good grasp of graph theory is very important for cracking coding interviews at MAANG. 

Check out this coding ninjas' blog on graph theory algorithms for getting a better hold on it.

To learn more about such data structures and algorithms, Coding Ninjas Studio is a one-stop destination. This platform will help you to improve your coding techniques and give you an overview of interview experiences in various product-based companies by providing Online Mock Test Series and many more benefits.

Happy learning!

 

 

Live masterclass