HackerRank DFS: Connected Cell in a Grid solution

YASH PAL,

In this HackerRank DFS: Connected Cell in a Grid Interview preparation kit problem there is Given an n x m matrix, find and print the number of cells in the largest region in the matrix.

HackerRank DFS: Connected Cell in a Grid solution

Problem solution in Python programming.

def getAdjacentNodes(matrix, i, j):
    s = set()
    if i - 1 >= 0:
        if matrix[i-1][j] == 1:
            s = s.union([(i-1, j)])
        if j - 1 >= 0:
            if matrix[i-1][j-1] == 1:
                s = s.union([(i-1, j-1)])
        
        if j + 1 < len(matrix[i]):
            if matrix[i-1][j+1] == 1:
                s = s.union([(i-1, j+1)])
        
    if i + 1 < len(matrix):
        if matrix[i+1][j] == 1:
            s = s.union([(i+1, j)])
        if j - 1 >= 0:
            if matrix[i+1][j-1] == 1:
                s = s.union([(i+1, j-1)])
        
        if j + 1 < len(matrix[i]):
            if matrix[i+1][j+1] == 1:
                s = s.union([(i+1, j+1)])
    
    if j - 1 >= 0:
        if matrix[i][j-1] == 1:
            s = s.union([(i, j-1)])
        
    if j + 1 < len(matrix[i]):
        if matrix[i][j+1] == 1:
            s = s.union([(i, j+1)]) 
    
    return s

def matrixToAdjacencyList(matrix):
    g = {}
    for i in range(len(matrix)):
        for j in range(len(matrix[i])):
            if matrix[i][j] == 1:
                g[(i, j)] = getAdjacentNodes(matrix, i, j)
    return g

def dfs(graph):
    def helper(start):
        visited, stack = set(), [start]
        while stack:
            vertex = stack.pop()
            if vertex not in visited:
                visited.add(vertex)
                stack.extend(graph[vertex] - visited)
        return len(visited)
    return helper
    
def getBiggestRegion(grid):
    graph = matrixToAdjacencyList(grid)
    sizes = []
    gdfs = dfs(graph)
    for i in range(len(grid)):
        for j in range(len(grid[i])):
            if grid[i][j] == 1:
                sizes.append(gdfs((i, j)))
    return max(sizes)

n = int(input().strip())
m = int(input().strip())
grid = []
for grid_i in range(n):
    grid_t = list(map(int, input().strip().split(' ')))
    grid.append(grid_t)
print(getBiggestRegion(grid))

Problem solution in Java Programming.

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    static boolean[] marked;
    static int[] id;
    static int[] size;
    static int count;
    private static int largestConnectedComponentCount(Graph g) {
        List<Integer> nodes = new ArrayList<>();
        int i = 0;
        for (boolean e : g.enabled) {
            if (e) { nodes.add(i); }
            i++;
        }

        marked = new boolean[g.enabled.length];
        id = new int[g.enabled.length];
        size = new int[g.enabled.length];
        count = 0;
        for (int v : nodes) {
            if (!marked[v]) {
                dfs(g, v);
                count++;
            }
        }
        
        return Arrays.stream(size).max().orElse(0);
    }

    // depth-first search
    private static void dfs(Graph g, int v) {
        marked[v] = true;
        id[v] = count;
        size[count]++;
        g.adj.get(v)
                .stream()
                .filter(w -> !marked[w])
                .forEach(w -> dfs(g, w));
    }

    private static class Graph {
        boolean[] enabled;
        List<Set<Integer>> adj;

        Graph(int size) {
            enabled = new boolean[size];
            adj = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                adj.add(new HashSet<>());
            }
         }
    }
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int i = 0;
        Graph g = new Graph(n * m);
        for(int row = 0; row < n; row++){
            for(int col = 0; col < m; col++) {
                int val = in.nextInt();
                if (val == 1) {
                    g.enabled[i] = true;

                    int prev = i - 1;
                    int upLeft = i - m - 1;
                    int up = i - m;
                    int upRight = i - m + 1;
                    if (col > 0 && g.enabled[prev]) {
                        g.adj.get(prev).add(i);
                        g.adj.get(i).add(prev);
                    }
                    if (col > 0 && row > 0 && g.enabled[upLeft]) {
                        g.adj.get(upLeft).add(i);
                        g.adj.get(i).add(upLeft);
                    }
                    if (row > 0 && g.enabled[up]) {
                        g.adj.get(up).add(i);
                        g.adj.get(i).add(up);
                    }
                    if (col < m - 1 && row > 0 && g.enabled[upRight]) {
                        g.adj.get(upRight).add(i);
                        g.adj.get(i).add(upRight);
                    }
                }
                i++;
            }
        }

        System.out.println(largestConnectedComponentCount(g));

    }
}

Problem solution in C++ programming.

#include<bits/stdc++.h>
using namespace std;
int a[10][10];

int count(int i,int j,int n, int m)
{
    int answer = 0;
    if(a[i][j] == 0)
    return 0;
    if(i<0 or j<0 or i>= n or j >=m)
    return 0;
    if(a[i][j] == 1)
    {
        answer++;
        a[i][j]--;
    }
    answer += count(i-1,j-1,n,m);
    answer += count(i-1,j,n,m);
    answer += count(i-1,j+1,n,m);
    answer += count(i,j-1,n,m);
    answer += count(i,j+1,n,m);
    answer += count(i+1,j-1,n,m);
    answer += count(i+1,j,n,m);
    answer += count(i+1,j+1,n,m);
    return answer;

}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            cin>>a[i][j];
    int max = -1,ans;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        {
            ans = count(i,j,n,m);
            if(ans > max)
            max = ans;
        }
    cout<<max;
    return 0;
}

Problem solution in C programming.

#include <stdio.h>
#include <stdint.h>
#include <string.h>

#define RUN_TEST_CASES(VAR) int VAR##_total; scanf("%d", & VAR##_total); 
	for(int VAR=1; VAR<=VAR##_total; ++VAR)

typedef unsigned long long ull;

int get_area_size(int matrix[10][10], int rows, int cols, int row, int col)
{
	if (row < 0 || row >= rows) return 0;
	if (col < 0 || col >= cols) return 0;
	if (matrix[row][col] != 1) return 0;
	
	matrix[row][col] = 0; // visited
	
	return 1
		+ get_area_size(matrix, rows, cols, row - 1, col - 1)
		+ get_area_size(matrix, rows, cols, row - 1, col)
		+ get_area_size(matrix, rows, cols, row - 1, col + 1)
		+ get_area_size(matrix, rows, cols, row, col - 1)
		+ get_area_size(matrix, rows, cols, row, col + 1)
		+ get_area_size(matrix, rows, cols, row + 1, col - 1)
		+ get_area_size(matrix, rows, cols, row + 1, col)
		+ get_area_size(matrix, rows, cols, row + 1, col + 1)
		;
}

int main()
{
#ifdef _DEBUG
	char FNAME[250];
	strcpy(FNAME, __FILE__);
	strcpy(strchr(FNAME, '.'), ".txt");
	freopen(FNAME, "rt", stdin);
#endif

	int matrix[10][10];

	int rows, cols;
	scanf("%d %d", &rows, &cols);

	for (int row = 0; row < rows; ++row)
		for (int col = 0; col < cols; ++col)
			scanf("%d", &matrix[row][col]);

	int largest_area = 0;

	for (int row = 0; row < rows; ++row)
	{
		for (int col = 0; col < cols; ++col)
		{
			if (matrix[row][col] != 1) continue;
			int area_size = get_area_size(matrix, rows, cols, row, col);
			if (area_size > largest_area)
				largest_area = area_size;
		}
	}

	printf("%d", largest_area);
}

Problem solution in JavaScript programming.

process.stdin.resume();
process.stdin.setEncoding('ascii');

var input_stdin = "";
var input_stdin_array = "";
var input_currentline = 0;

process.stdin.on('data', function (data) {
    input_stdin += data;
});

process.stdin.on('end', function () {
    input_stdin_array = input_stdin.split("n");
    main();    
});

function readLine() {
    return input_stdin_array[input_currentline++];
}

/////////////// ignore above this line ////////////////////


var isValid = function(x, y, n, m) {
    return (x >= 0 && y >= 0 && x < n && y < m);
}
var visit = function(x, y, grid, visited, n, m) {
    if (grid[x][y] === 1 && !visited[x][y]) {
        var count = 1;
        visited[x][y] = true;
        for (var i = x - 1; i <= x + 1; i++) {
            for (var j = y - 1; j <= y + 1; j++) {
                if (isValid(i, j, n, m)) {
                    count += visit(i, j, grid, visited, n, m);
                }
            }
        }
        return count;
    } else {
        return 0;
    }
}

function main() {
    var n = parseInt(readLine());
    var m = parseInt(readLine());
    var grid = [];
    for(grid_i = 0; grid_i < n; grid_i++){
       grid[grid_i] = readLine().split(' ');
       grid[grid_i] = grid[grid_i].map(Number);
    }
    
    var visited = [];
    for (var i = 0; i < grid.length; i++) {
        visited.push([]);
    }
    
    var max = 0;
    for (var i = 0; i < n; i++) {
        for (var j = 0; j < m; j++) {
            var count = visit(i, j, grid, visited, n, m);
            max = Math.max(count, max);
        }
    }
    console.log(max);
}

coding problems interview prepration kit