HackerRank Connected Cells in a Grid Solution

In this post, we will solve HackerRank Connected Cells in a Grid Problem Solution.

Consider a matrix where each cell contains either a 0 or a 1. Any cell containing a 1 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 n x m 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 3 x 3 matrix. The larger region at the top left contains 3 cells. The smaller one at the bottom right contains 1.

110
100
001

Function Description
Complete the connectedCell function in the editor below.
connected Cell has the following parameter(s):

int matrix[n][m]: matrix[i] represents the ¿th row of the matrix

Returns
-int: the area of the largest region
Input Format
The first line contains an integer n, the number of rows in the matrix.
The second line contains an integer m, the number of columns in the matrix.
Each of the next n lines contains m space-separated integers matrix[i][j].

Sample Input

STDIN       Function
-----       --------
4           n = 4
4           m = 4
1 1 0 0     grid = [[1, 1, 1, 0], [0, 1, 1, 0], [0, 0, 1, 0], [1, 0, 0, 0]]
0 1 1 0
0 0 1 0
1 0 0 0

Sample Output

Explanation

The diagram below depicts two regions of the matrix. Connected regions are filled with X or Y. Zeros are replaced with dots for clarity.

X X . .
. X X .
. . X .
Y . . .

The larger region has 5 cells, marked X.

HackerRank Connected Cells in a Grid Problem Solution

Connected Cells in a Grid C Solution

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int m, n, k, a[20][20];
void
recu(int i, int j)
{
 //  printf("%d %d\n", i, j);
    if (i - 1 >= 0 && a[i-1][j] == 1) {
        a[i-1][j] = k;
        recu(i-1, j);
    }
    
    if (i + 1 < m && a[i+1][j] == 1) {
        a[i+1][j] = k;
        recu(i+1, j);
    }
    
    if (j - 1 >= 0 && a[i][j-1] == 1) {
        a[i][j-1] = k;
        recu(i, j-1);
    }
    
    if (j + 1 < n && a[i][j+1] == 1) {
        a[i][j+1] = k;
        recu(i, j+1);
    }
    if (j + 1 < n && i + 1 < m && a[i+1][j+1] == 1) {
        a[i+1][j+1] = k;
        recu(i+1, j+1);
    }
    if (j - 1 >= 0 && i + 1 < m && a[i+1][j-1] == 1) {
        a[i+1][j-1] = k;
        recu(i+1, j-1);
    }
    if (j - 1 >= 0 && i - 1 > 0 && a[i-1][j-1] == 1) {
        a[i-1][j-1] = k;
        recu(i-1, j-1);
    }
    if (j + 1 < n && i - 1 > 0 && a[i-1][j+1] == 1) {
        a[i-1][j+1] = k;
        recu(i-1, j+1);
    }
        
    
}

int main() {
    int i, j, *arr;
    scanf ("%d%d", &m, &n);
    for(i= 0; i < m; i++) {
        for(j = 0; j < n; j++) {
            scanf("%d", &a[i][j]);
        }
    }
    k = 2;
    for(i= 0; i < m; i++) {
        for(j = 0; j < n; j++) {
            if (a[i][j] == 1) {
                a[i][j] = k;
                recu(i,j);
                k++;
            }
        }
    }
    arr = (int *)calloc(1, k * sizeof(int));
    for(i= 0; i < m; i++) {
        for(j = 0; j < n; j++) {
            if (a[i][j] != 0) {
                arr[a[i][j]] ++;
            }
            //printf("%d ", a[i][j]);
        }
        //printf("\n");
    }
    int max = -1;
    for (i = 0; i < k; i ++) {
        if (max < arr[i])
            max = arr[i];
    }
    
    free(arr);
    printf("%d\n", max);
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */    
    return 0;
}

Connected Cells in a Grid C++ Solution

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

int cc;

void rec(vector<vector<int> > &A, int i, int j, int prevC, int newC)
{
	if (i < 0 || i >= A.size() || j < 0 || j >= A[0].size())
	{
		return;
	}
	if (A[i][j] != prevC)
	{
		return;
	}

	cc++;
	A[i][j] = newC;

	rec(A, i + 1, j, prevC, newC);
	rec(A, i - 1, j, prevC, newC);
	rec(A, i, j + 1, prevC, newC);
	rec(A, i, j - 1, prevC, newC);
	rec(A, i + 1, j + 1, prevC, newC);
	rec(A, i + 1, j - 1, prevC, newC);
	rec(A, i - 1, j + 1, prevC, newC);
	rec(A, i - 1, j - 1, prevC, newC);
}

int main(void)
{
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	int m;
	cin >> m;
	int n;
	cin >> n;
	vector<vector<int> > A(m, vector<int>(n));
	for (int i = 0; i < m; i++)
	{
		for(int j = 0; j < n; j++)
		{
			cin >> A[i][j];
		}
	}

	int cmx = INT_MIN;

	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cc = 0;
			rec(A, i, j, 1, 2);
			cmx = max(cmx, cc);
		}
	}
	cout << cmx << endl;
	return 0;
}

Connected Cells in a Grid C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
class Solution {
        public class DepthFirstSearchGraph
        {
            // node class to store the state of each vertex while performing depth-first-search
            public class Node
            {
                public string name { set; get; }
                public bool visited { set; get; }

                public Node()
                {
                    this.name = String.Empty;
                    this.visited = false;
                }
            }

            // the maximum number of nodes this graph can contain
            public int maxNodes;

            // the adjacents lookup table that will help us navigate the graph
            public int[,] adjacents;

            // the vertices that shall be the nodes of our graph
            public List<Node> nodes;

            public DepthFirstSearchGraph(int maxNodes)
            {
                this.maxNodes = maxNodes;
                this.nodes = new List<Node>(maxNodes);
                this.adjacents = new int[maxNodes, maxNodes];

                // intializing all adjacent values as 0
                for (int i = 0; i < maxNodes; i++)
                    for (int j = 0; j < maxNodes; j++)
                        adjacents[i, j] = 0;
            }

            // function Dfs (depth first search): 
            // 1. navigating all graphs starting by a default node
            // 2. each node traversed is pushed into a stack (to know our way back to the original node)
            // 3. at a dead end, we go back, and find the next adjacent node (through the adjacents matrix)
            // 4. finally, we get all graphs and we find the maximum graph by points (number of nodes traversed)
            public void Dfs(int node)
            {
                bool allGraphNavigated = false;
                List<int> graphAreas = new List<int>(); 

                while (!allGraphNavigated)
                {
                    int area = 0;
                    int nextNode = node;
                    Stack<int> visits = new Stack<int>();

                    visits.Push(nextNode);
                    nodes[nextNode].visited = true;
                    area++;

                    while (visits.Count > 0)
                    {
                        nextNode = GetUnVisitedAdjacent(nextNode);

                        //Console.WriteLine("adjacent is: {0}", nextNode);

                        if (nextNode != -1)
                        {
                            area++;
                            visits.Push(nextNode);
                            nodes[nextNode].visited = true;

                            //Console.WriteLine("nextVertex is: {0}", nextNode);
                        }
                        else
                        {
                            //Console.WriteLine("popped is: {0}", visits.Peek());

                            nextNode = visits.Pop();
                        }
                    }

                    graphAreas.Add(area);

                    // we are trying to know if there any unvisited not, so we start a new grap traversing
                    if (nodes.Where(n => !n.visited).Any())
                        node = nodes.IndexOf(nodes.Where(n => !n.visited).First());
                    else
                        allGraphNavigated = true;
                }

                Console.WriteLine(graphAreas.Max());
            }

            // function AddVertex: inserting a new vertex, with the name (index of last vertex + 1)
            public void AddNode(String nodeName)
            {
                nodes.Add(new Node() { name = nodeName });
            }

            // function AddAdjacent: making the connection between two nodes to form an adjacent (node 0 <---> node 1)
            public void AddAdjacent(int node, int adjacent)
            {
                adjacents[node, adjacent] = 1;
                adjacents[adjacent, node] = 1;
            }

            // function AddAdjacent: making the connection between two nodes to form an adjacent by named nodes (node 0 <---> node 1)
            public void AddAdjacent(string node, string adjacent)
            {
                int nodeIndex = nodes.IndexOf(nodes.Where(n => n.name == node).First());
                int adjacentIndex = nodes.IndexOf(nodes.Where(n => n.name == adjacent).First());

                adjacents[nodeIndex, adjacentIndex] = 1;
                adjacents[adjacentIndex, nodeIndex] = 1;
            }

            // function GetUnVisitedAdjacent: looking up the adjacent matrix to find the next adjacent point to "vertex" that hasn't been visited
            private int GetUnVisitedAdjacent(int node)
            {
                if (node >= 0)
                    for (int i = 0; i < maxNodes; i++)
                        if (adjacents[node, i] == 1 && !nodes[i].visited)
                            return i;

                return -1;
            }
        }

        static void Main(string[] args)
        {
            // A depth first search algorith would work fine in the case of this problem. It was challenging because:
            // 1. The "adjacents" were not provided, and I had to extract them (provided as a form of a matrix)
            // 2. I have to calculate all graph paths in order get the biggest region

            int nodes = 0;
            int rows = int.Parse(Console.ReadLine());
            int columns = int.Parse(Console.ReadLine());
            int[,] matrix = new int[rows, columns];

            // getting input and counting the nodes
            for (int i = 0; i < rows; i++)
            {
                int[] values = Console.ReadLine().Split(' ').Select(a => int.Parse(a)).ToArray();

                for (int j = 0; j < values.Length; j++)
                {
                    nodes++;
                    matrix[i, j] = values[j];
                }
            }

            DepthFirstSearchGraph graph = new DepthFirstSearchGraph(nodes);

            // adding named nodes in order to refer to them later on when adding the adjacents
            for (int i = 0; i < rows; i++)
                for (int j = 0; j < columns; j++)
                    if (matrix[i, j] == 1)
                        graph.AddNode(i + "." + j);

            // extracting the adjacents, which got me into two traps (two fault submissions)
            for (int i = 0; i < rows; i++)
            {
                for (int j = 0; j < columns; j++)
                {
                    if (matrix[i, j] == 1)
                    {
                        if (i + 1 < rows)
                            if (matrix[i + 1, j] == 1)
                                graph.AddAdjacent(i + "." + j, (i + 1) + "." + j);

                        if (j + 1 < columns)
                            if (matrix[i, j + 1] == 1)
                                graph.AddAdjacent(i + "." + j, i + "." + (j + 1));

                        if (i + 1 < rows && j + 1 < columns)
                            if (matrix[i + 1, j + 1] == 1)
                                graph.AddAdjacent(i + "." + j, (i + 1) + "." + (j + 1));

                        if (i + 1 < rows && j - 1 >= 0)
                            if (matrix[i + 1, j - 1] == 1)
                                graph.AddAdjacent(i + "." + j, (i + 1) + "." + (j - 1));
                    }
                }
            }

            // starting the depth first search
            graph.Dfs(0);
        }
}

Connected Cells in a Grid Java Solution

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {

    /*
     * Complete the 'connectedCell' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts 2D_INTEGER_ARRAY matrix as parameter.
     */

    public static int connectedCell(List<List<Integer>> matrix) {
    // Write your code here
int max = 0, n = matrix.size(), m = matrix.get(0).size(); 
      for(int i=0; i < n; i++){
        for(int j=0; j < m; j++){
          if(matrix.get(i).get(j)==1){
             int temp[] = {0};  
             coverregion(matrix, i, j, n, m, temp);
             max = Integer.max(max, temp[0]);
          }        
        }     
     }     
    return max;    
    }
    
   static void coverregion(List<List<Integer>>mt, int i,int j, int n, int m, int c[]){
    if(i >= n || i < 0 || j >= m || j < 0)return;
    if(mt.get(i).get(j) == 0)return;
    
    mt.get(i).set(j, 0);
    c[0]++;
    
    coverregion(mt, i, j+1, n, m, c); 
    coverregion(mt, i, j-1, n, m, c); 
    coverregion(mt, i+1, j, n, m, c); 
    coverregion(mt, i-1, j, n, m, c); 
    coverregion(mt, i-1, j+1, n, m, c); 
    coverregion(mt, i+1, j+1, n, m, c); 
    coverregion(mt, i+1, j-1, n, m, c); 
    coverregion(mt, i-1, j-1, n, m, c);  
    }

}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int n = Integer.parseInt(bufferedReader.readLine().trim());

        int m = Integer.parseInt(bufferedReader.readLine().trim());

        List<List<Integer>> matrix = new ArrayList<>();

        IntStream.range(0, n).forEach(i -> {
            try {
                matrix.add(
                    Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
                        .map(Integer::parseInt)
                        .collect(toList())
                );
            } catch (IOException ex) {
                throw new RuntimeException(ex);
            }
        });

        int result = Result.connectedCell(matrix);

        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();

        bufferedReader.close();
        bufferedWriter.close();
    }
}

Connected Cells in a Grid JavaScript Solution

function dfs(i,j,a,u){
    
    //console.log(i+" "+j);
    u[i][j]=1;
    for(var ii=i-1;ii<=i+1;ii++)
        for(var jj=j-1;jj<=j+1;jj++)
            if(ii>=0 && jj>=0 && ii<a.length && jj<a[0].length && a[ii][jj] && !u[ii][jj])
                dfs(ii,jj,a,u);
}

function processData(input) {
    var data=input.split('\n');
    var n=parseInt(data[0],10);
    var m=parseInt(data[1],10);
    var a=[];
    for(var i=0;i<n;i++) {
        a.push([]);
        var arr=data[i+2].split(' ');
        for(var j=0;j<m;j++)
            a[i].push(arr[j].indexOf('1')!==-1?1:0);
        //console.log(a[i]);
    }
    var u=[];
    for(var i=0;i<n;i++){
        u[i]=[];
        for(var j=0;j<m;j++)
            u[i][j]=0;
    }
    var ans=0;
    var cur=0;
    for(var i=0;i<n;i++)
        for(var j=0;j<m;j++)
            if(!u[i][j] && a[i][j])
            {
                var i1=i;
                var j1=j;
                dfs(i1,j1,a,u);
                var next=0;
                for(var k=0;k<n;k++)
                    for(var l=0;l<m;l++)
                        if(u[k][l]){
                            //console.log(k+" "+l);
                            next++;
                        }
                ans=Math.max(next-cur,ans);
                cur=next;
            }
    console.log(ans);
} 

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});

Connected Cells in a Grid Python Solution

import sys

number_of_rows = int(sys.stdin.readline())
number_of_columns = int(sys.stdin.readline())
grid = []

for row in range(number_of_rows):
    row = sys.stdin.readline().strip('\s\n').split()
    grid.append(row)

path_grid = [[set() for x in range(number_of_columns)] for x in range(number_of_rows)]
overall_max_area = int(0)

for current_row in range(number_of_rows):
    for current_column in range(number_of_columns):
        if (grid[current_row][current_column] != '0'):
            max_path = set([(current_row, current_column)])
            # Check for any connection from the row above
            for last_column in range(current_column - 1, current_column + 2):
                if (last_column >= 0 and last_column < number_of_columns):
                    max_path = max_path.union(path_grid[current_row - 1][last_column])
            # Check for connection from the column on the left
            if (current_column > 0 and len(path_grid[current_row][current_column - 1])):
                max_path = max_path.union(path_grid[current_row][current_column - 1])
            # Check for connection from row above that is not directly connected
            for last_column in range(0, current_column - 1):
                if (len(path_grid[current_row - 1][last_column])):
                    difference = path_grid[current_row - 1][last_column].difference(max_path)
                    if (len(difference) < len(path_grid[current_row - 1][last_column])):
                        max_path.update(difference)
            for last_column in range(current_column + 2, number_of_columns):
                if (len(path_grid[current_row - 1][last_column])):
                    difference = path_grid[current_row - 1][last_column].difference(max_path)
                    if (len(difference) < len(path_grid[current_row - 1][last_column])):
                        max_path.update(difference)
            # Check for connection from the columns on the left that is not directly connected
            for last_column in range(0, current_column - 1):
                if (len(path_grid[current_row][last_column])):
                    difference = path_grid[current_row][last_column].difference(max_path)
                    if (len(difference) < len(path_grid[current_row][last_column])):
                        max_path.update(difference)

            path_grid[current_row][current_column] = max_path

            if (len(path_grid[current_row][current_column]) > overall_max_area):
                overall_max_area = len(path_grid[current_row][current_column])

print(overall_max_area)

c C# C++ HackerRank Solutions java javascript python C cpp CSharp Hackerrank Solutions java javascript python