Hackerrank Connected Cells in a Grid Solution
.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}
Consider a matrix where each cell contains either a or a . Any cell containing a is called a filled cell. Two cells are said to be connected if they are adjacent to each other horizontally, vertically, or diagonally. In the following grid, all cells marked X are connected to the cell marked Y.
XXX
XYX
XXX
If one or more filled cells are also connected, they form a region. Note that each cell in a region is connected to zero or more cells in the region but is not necessarily directly connected to all the other cells in the region.
Given an matrix, find and print the number of cells in the largest region in the matrix. Note that there may be more than one region in the matrix.
For example, there are two regions in the following matrix. The larger region at the top left contains cells. The smaller one at the bottom right contains .
110
100
001
Function Description
Complete the connectedCell function in the editor below. It should return an integer that denotes the area of the largest region.
connectedCell has the following parameter(s):
- matrix: a 2D array of integers where represents the row of the matrix
Input Format.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}
The first line contains an integer , the number of rows in the matrix.
The second line contains an integer , the number of columns in the matrix.
Each of the next lines contains space-separated integers .
Constraints.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue}
Output Format.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue}
Print the number of cells in the largest region in the given matrix.
Sample Input.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue}
4
4
1 1 0 0
0 1 1 0
0 0 1 0
1 0 0 0
Sample Output.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue}
5
Explanation.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}
The diagram below depicts two regions of the matrix; for each region, the component cells forming the region are marked with an X:
X X 0 0 1 1 0 0
0 X X 0 0 1 1 0
0 0 X 0 0 0 1 0
1 0 0 0 X 0 0 0
The first region has five cells and the second region has one cell. We print the size of the largest region.
Solution in java8
Approach 1.
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
static int rs(int[][] matrix , int i , int j){
if(i<0 || j<0 || i >= matrix.length || j >= matrix[i].length)
return 0;
if(matrix[i][j] == 0)
return 0;
int size = 1;
matrix[i][j] = 0;
for(int r = i-1; r<=i+1;r++){
for(int c = j-1; c <= j+1; c++){
if(r != i || c != j){
size += rs(matrix,r,c);
}
}
}
return size;
}
static int connectedCell(int[][] matrix,int n , int m ) {
int max = 0;
for(int i = 0 ;i<n;i++){
for(int j = 0 ;j<m;j++){
if(matrix[i][j] == 1){
int size = rs(matrix , i ,j);
max = Math.max(size , max);
}
}
}
return max;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int[][] matrix = new int[n][m];
for(int matrix_i = 0; matrix_i < n; matrix_i++){
for(int matrix_j = 0; matrix_j < m; matrix_j++){
matrix[matrix_i][matrix_j] = in.nextInt();
}
}
int result = connectedCell(matrix,n,m);
System.out.println(result);
in.close();
}
}
Approach 2.
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
private static int countCells(int[][] matrix, int i, int j) {
if (i < 0 || j < 0 || i >= matrix.length || j >= matrix[0].length) return 0;
if (matrix[i][j] == 0) return 0;
int count = matrix[i][j]--;
count += countCells(matrix, i + 1, j);
count += countCells(matrix, i - 1, j);
count += countCells(matrix, i, j + 1);
count += countCells(matrix, i, j - 1);
count += countCells(matrix, i + 1, j + 1);
count += countCells(matrix, i - 1, j - 1);
count += countCells(matrix, i - 1, j + 1);
count += countCells(matrix, i + 1, j - 1);
return count;
}
public static int getBiggestRegion(int[][] matrix) {
int max = 0;
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
max = Math.max(max, countCells(matrix, i, j));
}
}
return max;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int grid[][] = new int[n][m];
for(int grid_i=0; grid_i < n; grid_i++){
for(int grid_j=0; grid_j < m; grid_j++){
grid[grid_i][grid_j] = in.nextInt();
}
}
System.out.println(getBiggestRegion(grid));
}
}
Approach 3.
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
static int[][] neighbours(int i, int j){
return new int[][]{
{i,j+1},{i,j-1},
{i+1,j},{i+1,j+1},{i+1, j-1},
{i-1,j},{i-1,j-1},{i-1, j-1}
};
}
static int newRegion(int[][] matrix, int i, int j){
if(matrix[i][j] != 1)
return 0;
int n = matrix.length, m = matrix[0].length, counter = 0;
List<int[]> cells = new ArrayList<int[]>();
cells.add(new int[]{i, j});
while(cells.size() > 0){
int[] coords = cells.remove(0);
i = coords[0];
j = coords[1];
if(i >= 0 && i < n && j >= 0 && j < m && matrix[i][j] == 1){
matrix[i][j] = 2;
int[][] neigh = neighbours(i, j);
cells.addAll(Arrays.asList(neigh));
++counter;
}
}
return counter;
}
static int connectedCell(int[][] matrix) {
int max_region = 0;
for(int i = 0; i < matrix.length; ++i)
for(int j = 0; j < matrix[0].length; ++j)
max_region = Math.max(max_region, newRegion(matrix, i, j));
return max_region;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int[][] matrix = new int[n][m];
for(int matrix_i = 0; matrix_i < n; matrix_i++){
for(int matrix_j = 0; matrix_j < m; matrix_j++){
matrix[matrix_i][matrix_j] = in.nextInt();
}
}
int result = connectedCell(matrix);
System.out.println(result);
in.close();
}
}
Solution in python3
Approach 1.
n=int(input())
m=int(input())
l=[]
for i in range(n):
l.append(list(map(int,input().split())))
def check(i,j):
if i<0 or j<0 or i>=n or j>=m or l[i][j]==-1 or l[i][j]==0:
return 0
else:
l[i][j]=-1
return 1+(check(i,j+1)+check(i,j-1)+check(i+1,j)+check(i-1,j+1)+check(i-1,j-1)+check(i,j+1)+check(i+1,j-1)+check(i+1,j+1))
res= -1
for i in range(n):
for j in range(m):
if l[i][j]==1:
res=max(res,check(i,j))
print(res)
Approach 2.
#!/bin/python3
import math
import os
import random
import re
import sys
# Complete the connectedCell function below.
def connectedCell(matrix):
mx = 0
filled = [(i, j) for i, row in enumerate(matrix) for j,n in enumerate(row) if n]
while filled:
region = [filled.pop()]
count = 0
while region:
n = region.pop()
count += 1
for f in list(filled):
if abs(n[0] - f[0]) <= 1 and abs(n[1]-f[1]) <= 1:
region.append(f)
filled.remove(f)
else:
mx = max(mx, count)
return mx
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
n = int(input())
m = int(input())
matrix = []
for _ in range(n):
matrix.append(list(map(int, input().rstrip().split())))
result = connectedCell(matrix)
fptr.write(str(result) + '\n')
fptr.close()
Approach 3.
#!/bin/python3
import math
import os
import random
import re
import sys
# Complete the connectedCell function below.
def dfs(matix, i, j, m, n, size):
matrix[i][j] = 0
dis = [(0, -1), (0, 1), (-1, 0), (1, 0), (-1, -1), (1, 1), (-1, 1), (1, -1)]
for di in dis:
n_i = i + di[0]
n_j = j + di[1]
if 0 <= n_i < m and 0 <= n_j < n and matrix[n_i][n_j] == 1:
size = dfs(matrix, n_i, n_j, m, n, size+1)
return size
def connectedCell(matrix):
m = len(matrix)
n = len(matrix[0])
max_size = 0
for i in range(m):
for j in range(n):
if matrix[i][j] == 1:
size = dfs(matrix, i, j, m, n, 1)
max_size = max(size, max_size)
return max_size
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
n = int(input())
m = int(input())
matrix = []
for _ in range(n):
matrix.append(list(map(int, input().rstrip().split())))
result = connectedCell(matrix)
fptr.write(str(result) + '\n')
fptr.close()
Solution in cpp
Approach 1.
Approach 2.
#include <bits/stdc++.h>
using namespace std;
struct _ { _() { cin.sync_with_stdio(0), cin.tie(0); } }_;
int arr[11][11];
int m = 0, n = 0;
int ff(int i, int j) {
if (i < 0 || i >= m || j < 0 || j >= n
|| arr[i][j] == -1 || arr[i][j] == 1)
return 0;
else {
arr[i][j] = 1;
return 1 + ff(i+1, j) + ff(i-1, j) +
ff(i, j+1) + ff(i, j-1) +
ff(i+1, j-1) + ff(i-1, j+1) +
ff(i+1, j+1) + ff(i-1, j-1);
}
}
int main() {
cin >> m >> n;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
int x; cin >> x;
arr[i][j] = x-1;
// -1 = 0s, 0 = unvisited 1s, 1 = visited 1s
}
}
int mx = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (arr[i][j] == 0)
mx = max(mx, ff(i, j));
}
}
cout << mx;
return 0;
}Approach 3.
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int quant[100] = {0};
void pinta(int a[12][12], int x, int y, int atual)
{
a[x][y] = atual;
quant[atual]++;
for (int i = x-1; i <= x+1; i++) {
for (int j = y-1; j <= y+1; j++) {
if ((i != x or j != y) and a[i][j] == 1)
pinta(a, i, j, atual);
}
}
}
int main()
{
int m, n;
cin >> m >> n;
int a[12][12] = {0};
int atual = 2;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
cin >> a[i][j];
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (a[i][j] == 1) {
pinta(a, i, j, atual);
atual++;
}
}
}
int maximo = 0;
for (int i = 0; i < 100; i++) {
if (quant[i] > maximo) maximo = quant[i];
}
printf("%d\n", maximo);
return 0;
}