Interview Question Software Engineer / Developers
Country: United States
Interview Type: In-Person
This is what is known as floodfill, an application of DFS. For each element in the array that is a 1 you attempt to recursively search all 4 neighbors for 1s, the search continues till you either hit the boundaries or see 0s. Also as and when you find 1s you make them 0s so that they are not counted again. Repeat this search for every element
Code
public static int countIslands(int[][] matrix) {
if (matrix == null || matrix.length == 0) return 0;
int result = 0;
for (int i=0; i<matrix.length; i++) {
for (int j=0; j<matrix[i].length; j++) {
if (matrix[i][j] == 1) {
result++;
doFill(matrix, i, j);
}
}
}
return result;
}
public static void doFill(int[][] matrix, int row, int col) {
if (row < 0 || col < 0 || row >= matrix.length || col >=matrix[0].length || matrix[row][col] == 0) {
return;
}
matrix[row][col] = 0;
int dr[] = {-1,0,1,0};
int dc[] = {0,1,0,-1};
for (int i=0; i<dr.length; i++) {
doFill(matrix, row + dr[i], col + dc[i]);
}
}
To make this work for extremely large matrices, you would replace recursion with an explicitly maintained stack or queue (rather than using the recursion stack). Instead of recursing you would add candidates to this data structure and keep popping them off and processing them till the stack is empty
can you please explain a little more on the explicitly maintained stack and how would it be more efficient than the recursive stack? is it just because the recursive stack will maintain local variables at each recursion?
Similar to grassfire algorithm.
could go through the matrix from left top and check if the value is 1, then call grass fire algorithm to recursively find adjacent 1s. remember to be more efficient put a flag on each node that is visited.
in this case run time would be o(n + m) which n is the number of elements in matrix and m is the number of 1s. in the worst case o(2n) which is linear
One could have a collection of Groups, each Group containing a set of [x,y] points.
scan from top-left by rows, visiting each cell only once.
when you find a 1 at [x,y], see if Points [x-1,y] or [x, y-1] belong to any existing group,
if so, add [x,y] to that group;
if the two query points belong to two different groups, then merge those two groups.
if the new point [x,y] is not adjacent to an existing group, start a new group to contain it.
In a single scan of the matrix (visit/evaluate each cell only once)
you get the collection of [disjoint] groups, each with a set of adjacent point.
The space complexity is proportional to the number of 1s in the matrix,
the time complexity depends on the layout, but worst case you are looking up the 1s in each of the disjoint groups, so O(n*g) for n 1s in g Groups.
If you have a large sparse-matrix representation, this is quite efficient.
[i also used this algorithm for analyzing a Go board...]
/* Ref: en.wikipedia.org/wiki/Flood_fill, youtube.com/watch?v=kV-l8Gnwtkk
* geeksforgeeks.org/find-number-of-islands/
*/
int rowMax;int colMax;
//boolean visited[][]= null;
public int countIslands(int[][] arr, int m, int n){
boolean visited[][] = new boolean[m][n];
rowMax = m; colMax=n;
for(int i =0; i<=m; i++){ //make a boolean array to mark the visited cell
for(int j =0; j<=m; j++){
visited[i][j]= false;
}
}
int count =0; //cluster count
for(int i =0; i<=m; i++){
for(int j =0; j<=m; j++){
if(arr[i][j] == 1 && ! visited[i][j]){// cell value =1 and cell not visited
traverseDFS(arr, i, j, visited); //completes a patch / cluster / island / fill a shape recursively
++count;
}
}
}
return count;
}
class Grid{
int x; int y;
public Grid(int x, int y) {
this.x =x; this.y=y;
}
}
public Map<Integer,List<Grid>> getAllIlands(int[][] arr, int m, int n){
boolean visited[][] = new boolean[m][n];
rowMax = m; colMax=n;
for(int i =0; i<=m; i++){ //make a boolean array to mark the visited cell
for(int j =0; j<=m; j++){
visited[i][j]= false;
}
}
int clusterId =0; //cluster count
List<Grid> cluster = new ArrayList<Grid>();
Map<Integer,List<Grid>> map = new HashMap<Integer,List<Grid>>();
for(int i =0; i<=m; i++){
for(int j =0; j<=m; j++){
if(arr[i][j] == 1 && ! visited[i][j]){// cell value =1 and cell not visited
traverseDFS(arr, i, j, visited, cluster); //completes a patch / cluster / island / fill a shape recursively
++clusterId;
map.put(clusterId, cluster);
cluster = new ArrayList<Grid>();
}
}
}
return map;
}
// To go for {8 - fill} or {4-fill} as per situation
private void traverseDFS(int[][] arr, int i, int j, boolean[][] visited,
List<Grid> cluster) {
int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1}; // 0 <= |x-x'| <= 1
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1}; // 0 <= |y-y'| <= 1
visited[i][j]= true;
for(int k= 0; k<8; k++){
if(canVisit(arr, i+dx[k], j+dy[k], visited)){
cluster.add(new Grid(i+dx[k], j+dy[k]));
traverseDFS(arr, i+dx[k], j+dy[k], visited, cluster) ;
}
}
}
// reduce the number of arguments - recursion is heavy
private void traverseDFS(int[][] arr, int i, int j, boolean[][] visited) {
int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1}; // 0 <= |x-x'| <= 1
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1}; // 0 <= |y-y'| <= 1
visited[i][j]= true;
for(int k= 0; k<8; k++){
if(canVisit(arr, i+dx[k], j+dy[k], visited)){
traverseDFS(arr, i+dx[k], j+dy[k], visited) ;
}
}
}
private boolean canVisit(int[][] arr, int i, int j, boolean[][] visited) {
return (i >= 0) && (i < rowMax) && // row number is in range
(j >= 0) && (j < colMax) && // column number is in range
((arr[i][j]==1) && !visited[i][j]); // value is 1 and not yet visited
}
Javascript implementation using disjoint set with linked lists
var input = '5\nYYNNN\nYYYNN\nNYYNN\nNNNYN\nNNNNY'
console.log(input);
//above solution should be 3 because the components are
//{0,1,2}, because {0,1} and {1,2} therefore {0,1,2}
//{3}
//{4}
//MIT license, authored by Ling Qing Meng
//'4\nYYNN\nYYYN\nNYYN\nNNNY'
//Read Input, preformatting
var reformat = input.split(/\n/);
var N = reformat[0];
var adjMatrix = [];
for (var i = 1; i < reformat.length; i++) {
adjMatrix.push(reformat[i]);
}
//for (each person x from 1 to N) CREATE-SET(x)
var sets = [];
for (var i = 0; i < N; i++) {
var s = new LinkedList();
s.add(i);
sets.push(s);
}
//populate friend potentials using combinatorics, then filters
var people = [];
var friends = [];
for (var i = 0; i < N; i++) {
people.push(i);
}
var potentialFriends = k_combinations(people,2);
for (var i = 0; i < potentialFriends.length; i++){
if (isFriend(adjMatrix,potentialFriends[i]) === 'Y'){
friends.push(potentialFriends[i]);
}
}
//for (each pair of friends (x y) ) if (FIND-SET(x) != FIND-SET(y)) MERGE-SETS(x, y)
for (var i = 0; i < friends.length; i++) {
var x = friends[i][0];
var y = friends[i][1];
if (FindSet(x) != FindSet(y)) {
sets.push(MergeSet(x,y));
}
}
for (var i = 0; i < sets.length; i++) {
//sets[i].traverse();
}
console.log('How many distinct connected components?',sets.length);
//Linked List data structures neccesary for above to work
function Node(){
this.data = null;
this.next = null;
}
function LinkedList(){
this.head = null;
this.tail = null;
this.size = 0;
// Add node to the end
this.add = function(data){
var node = new Node();
node.data = data;
if (this.head == null){
this.head = node;
this.tail = node;
} else {
this.tail.next = node;
this.tail = node;
}
this.size++;
};
this.contains = function(data) {
if (this.head.data === data)
return this;
var next = this.head.next;
while (next !== null) {
if (next.data === data) {
return this;
}
next = next.next;
}
return null;
};
this.traverse = function() {
var current = this.head;
var toPrint = '';
while (current !== null) {
//callback.call(this, current); put callback as an argument to top function
toPrint += current.data.toString() + ' ';
current = current.next;
}
console.log('list data: ',toPrint);
}
this.merge = function(list) {
var current = this.head;
var next = current.next;
while (next !== null) {
current = next;
next = next.next;
}
current.next = list.head;
this.size += list.size;
return this;
};
this.reverse = function() {
if (this.head == null)
return;
if (this.head.next == null)
return;
var currentNode = this.head;
var nextNode = this.head.next;
var prevNode = this.head;
this.head.next = null;
while (nextNode != null) {
currentNode = nextNode;
nextNode = currentNode.next;
currentNode.next = prevNode;
prevNode = currentNode;
}
this.head = currentNode;
return this;
}
}
/**
* GENERAL HELPER FUNCTIONS
*/
function FindSet(x) {
for (var i = 0; i < sets.length; i++){
if (sets[i].contains(x) != null) {
return sets[i].contains(x);
}
}
return null;
}
function MergeSet(x,y) {
var listA,listB;
for (var i = 0; i < sets.length; i++){
if (sets[i].contains(x) != null) {
listA = sets[i].contains(x);
sets.splice(i,1);
}
}
for (var i = 0; i < sets.length; i++) {
if (sets[i].contains(y) != null) {
listB = sets[i].contains(y);
sets.splice(i,1);
}
}
var res = MergeLists(listA,listB);
return res;
}
function MergeLists(listA, listB) {
var listC = new LinkedList();
listA.merge(listB);
listC = listA;
return listC;
}
//access matrix by i,j -> returns 'Y' or 'N'
function isFriend(matrix, pair){
return matrix[pair[0]].charAt(pair[1]);
}
function k_combinations(set, k) {
var i, j, combs, head, tailcombs;
if (k > set.length || k <= 0) {
return [];
}
if (k == set.length) {
return [set];
}
if (k == 1) {
combs = [];
for (i = 0; i < set.length; i++) {
combs.push([set[i]]);
}
return combs;
}
// Assert {1 < k < set.length}
combs = [];
for (i = 0; i < set.length - k + 1; i++) {
head = set.slice(i, i+1);
tailcombs = k_combinations(set.slice(i + 1), k - 1);
for (j = 0; j < tailcombs.length; j++) {
combs.push(head.concat(tailcombs[j]));
}
}
return combs;
}
public class MatrixClass {
public static void main(String[] args) {
int[][] arr = new int[][] {
{1,1,0,1},
{1,1,1,0},
{1,1,0,0},
{1,1,0,0}
};
checkMatrix(arr);
}
public static void checkMatrix(int[][] matrix) {
int row = matrix.length;
int col = matrix[0].length;
int count_1s = 0;
int count_0s = 0;
for(int i=0; i<row; i++)
{
int temp = matrix[i][0];
int count=0;
for(int j=0; j<col; j++) {
if(temp == matrix[i][j]) {
count++;
}
}
if(count == col && temp == 1) {
count_1s++;
} else if(count == col && temp == 0) {
count_0s++;
}
}
for(int i=0; i<col; i++)
{
int temp = matrix[0][i];
int count=0;
for(int j=0; j<row; j++) {
if(temp == matrix[j][i]) {
count++;
}
}
if(count == row && temp == 1) {
count_1s++;
} else if(count == row && temp == 0) {
count_0s++;
}
}
System.out.println("O's: " + count_0s + " , 1's: " + count_1s);
}
}
I solved through DFS approach
public class NumberOfGroupOf_1 {
public static int row =0;
public static int col =0;
public static void main(String[] args) {
int matrix[][]= new int[][]{
{1, 1, 0, 0, 0},
{0, 1, 0, 0, 1},
{1, 0, 0, 1, 1},
{0, 0, 0, 0, 0},
{1, 0, 1, 0, 1}
};
row = matrix.length;
col = matrix[0].length;
boolean [][] visited= new boolean[row][col];
System.out.println(groupOfOne(matrix, visited));
}
private static int groupOfOne(int [][] matrix, boolean [][] visited){
int groupOfOne =0;
for(int i=0; i<row; i++){
for(int j=0; j<col; j++){
if(matrix[i][j]==1 && !visited[i][j]){
dfs(matrix, i, j, visited);
groupOfOne++;
}
}
}
return groupOfOne;
}
private static void dfs(int [][]matrix, int i, int j, boolean [][] visited){
int rowNbr[] = new int[] {-1, 0, 0, 1};
int colNbr[] = new int[] { 0, -1, 1, 0};
visited[i][j] = true;
for(int k=0; k<4; k++){
int x = rowNbr[k]+i;
int y = colNbr[k]+j;
if(isSafe(matrix, visited, x, y)){
dfs(matrix, x, y, visited);
}
}
}
private static boolean isSafe(int [][] matrix, boolean [][] visited, int i, int j){
if((i>=0 && i<col) && (j>=0 && j<row) && !visited[i][j] && matrix[i][j]==1){
return true;
}else {
return false;
}
}
}
int main() {
int m,n;
int a[100] [100];
bool found = false;
cout << " m & n :" ;
cin>>m >>n;
cout<<" Enter matrix elements : ";
for (int i = 0; i < m; i++) {
for (int j = 0 ; j < n ; j++) {
cin>>a[i][j];
}
}
int xiter [] = { 1, 0 , -1 ,0 };
int yiter [] = { 0, 1 , 0 ,-1 };
int island_count = 0;
for (int i=1 ; i < m -1; i++)
for (int j = 1; j < n-1; j++)
if (a[i][j] == 1) {
found = true;
for (int k =0 ; k < 4; k++) {
int x = i + xiter[k];
int y = j + yiter[k];
if (a[x][y] != 0) {
found = false;
break;
}
}
if (found) {
cout << "Island found at "<<i <<", "<<j<<endl;
}
}
// Count number of islands - 1 surrounded by 0
for (int i =0 ; i < m; i++)
for (int j = 0; j < n; j++) {
if (a[i][j] == 1) {
bool island = true;
a[i][j] = 2;
for (int k = 0; k < 4; k++) {
int x = i+ xiter[k];
int y = j + yiter[k];
if (x < 0 || y < 0 || x >=m || y>= n)
continue;
if (a[x][y] == 1) {
a[x][y] = 2;
} else if (a[x][y] == 2) {
island = false;
}
}
if (island)
island_count++;
}
}
cout << " Number of islands : " <<island_count <<endl;
return 0;
}
C++ Implementation:
#include <iostream>
using namespace std;
int main() {
int m,n;
int a[100] [100];
bool found = false;
cout << " m & n :" ;
cin>>m >>n;
cout<<" Enter matrix elements : ";
for (int i = 0; i < m; i++) {
for (int j = 0 ; j < n ; j++) {
cin>>a[i][j];
}
}
int xiter [] = { 1, 0 , -1 ,0 };
int yiter [] = { 0, 1 , 0 ,-1 };
int island_count = 0;
// Count number of islands -
for (int i =0 ; i < m; i++)
for (int j = 0; j < n; j++) {
if (a[i][j] == 1) {
bool island = true;
a[i][j] = 2;
for (int k = 0; k < 4; k++) {
int x = i+ xiter[k];
int y = j + yiter[k];
if (x < 0 || y < 0 || x >=m || y>= n)
continue;
if (a[x][y] == 1) {
a[x][y] = 2;
} else if (a[x][y] == 2) {
island = false;
}
}
if (island)
island_count++;
}
}
cout << " Number of islands : " <<island_count <<endl;
return 0;
}
int main() {
int m,n;
int a[100] [100];
bool found = false;
cout << " m & n :" ;
cin>>m >>n;
cout<<" Enter matrix elements : ";
for (int i = 0; i < m; i++) {
for (int j = 0 ; j < n ; j++) {
cin>>a[i][j];
}
}
int xiter [] = { 1, 0 , -1 ,0 };
int yiter [] = { 0, 1 , 0 ,-1 };
bool** land = new bool*[m];
for (int i=0; i < n; i++ )
land[i] = new bool[n];
for (int i = 0; i < m ; i++)
for (int j = 0; j < n; j++)
land[i] [j] = false;
int island_count = 0;
for (int i =0 ; i < m; i++)
for (int j = 0; j < n; j++) {
if (a[i][j] == 1 && !land[i][j]) {
bool island = true;
land[i][j] = true;
for (int k = 0; k < 4; k++) {
int x = i+ xiter[k];
int y = j + yiter[k];
if (x < 0 || y < 0 || x >=m || y>= n)
continue;
if (a[x][y] == 1) {
if (land[x][y]) {
//already visited
island = false;
} else {
land[x][y] = true;
}
}
}
if (island)
island_count++;
}
}
cout << " Number of islands : " <<island_count <<endl;
Return 0;
}
import java.util.Scanner;
//6 5
//1 1 1 0 0
//1 1 1 0 0
//1 1 1 0 0
//0 0 0 1 1
//0 0 1 0 1
//1 1 0 1 0
//5
//
//2 2
//1 0
//0 1
//2
public class 在01矩阵中找到1块 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int m = sc.nextInt();
int n = sc.nextInt();
int[][] a = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
a[i][j] = sc.nextInt();
}
}
System.out.println(count(a));
}
sc.close();
}
private static int count(int[][] arr) {
int count = 0;
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr[i].length; j++) {
count += (mark(arr, i, j) >= 1) ? 1 : 0;
}
}
return count;
}
private static int mark(int[][] arr, int i, int j) {
int count = 0;
if (i >= 0 && j >= 0 && i < arr.length && j < arr[i].length && arr[i][j] == 1) {
count++;
arr[i][j] = -1;
count += mark(arr, i + 1, j);
count += mark(arr, i - 1, j);
count += mark(arr, i, j + 1);
count += mark(arr, i, j - 1);
}
return count;
}
}
matrix = [
[0, 0, 1, 0, 0, 1],
[0, 0, 1, 0, 0, 1],
[0, 1, 1, 1, 0, 1],
[0, 0, 1, 0, 0, 1],
]
# first, convert the 1/0 matrix into an adjacency matrix represented by a map
graph = {}
def get_key(row, column):
return f'a{row}{column}'
for row in range(0, len(matrix)):
for column in range(0, len(matrix[0])):
key = get_key(row, column)
if key not in graph:
graph[key] = []
if column < len(matrix[0]) - 1 and matrix[row][column] == 1 and matrix[row][column + 1] == 1:
graph[key].append(get_key(row, column+1))
if column >= 1 and matrix[row][column] == 1 and matrix[row][column - 1] == 1:
graph[key].append(get_key(row, column - 1))
if row < len(matrix) - 1 and matrix[row][column] == 1 and matrix[row+1][column] == 1:
graph[key].append(get_key(row+1, column))
if row >= 1 and matrix[row][column] == 1 and matrix[row-1][column] == 1:
graph[key].append(get_key(row-1, column))
print(graph)
visited = set() # Set to keep track of visited nodes.
# You can also use BFS, too.
def dfs(visited, graph, node):
if node not in visited:
print (node)
visited.add(node)
for neighbour in graph[node]:
dfs(visited, graph, neighbour)
# counting the connected components
counter = 0
for node in graph.keys():
if node not in visited and len(graph[node]) > 0:
counter += 1
print(f"connected_component: #{counter}")
dfs(visited, graph, node)
- Michael Papadopoulos November 01, 2012public class Solution { public static void main(String[] args) { int[][] A = new int[1000][1000]; int cnt = 0; int cur_cnt = 0; for(int x=0; x<A.length; x++) { for(int y=0; y<A[x].length; y++) { A[x][y] = (int) Math.round(Math.random()); } } for(int x=0; x<A.length; x++) { for(int y=0; y<A[x].length; y++) { if (A[x][y] == 1) { cur_cnt = 0; cnt = cnt + clean_block(A,x,y, cur_cnt); } } } System.out.println(cnt); } public static int clean_block(int[][] A, int x_in, int y_in, int cur_cnt) { A[x_in][y_in] = 0; if (coordinate_exists(x_in-1,y_in , A.length, A[0].length) == 1 && A[x_in-1][y_in ] == 1) {clean_block(A,x_in-1,y_in ,cur_cnt); cur_cnt = 1;} if (coordinate_exists(x_in+1,y_in , A.length, A[0].length) == 1 && A[x_in+1][y_in ] == 1) {clean_block(A,x_in+1,y_in ,cur_cnt); cur_cnt = 1;} if (coordinate_exists(x_in ,y_in-1, A.length, A[0].length) == 1 && A[x_in ][y_in-1] == 1) {clean_block(A,x_in ,y_in-1,cur_cnt); cur_cnt = 1;} if (coordinate_exists(x_in ,y_in+1, A.length, A[0].length) == 1 && A[x_in ][y_in+1] == 1) {clean_block(A,x_in ,y_in+1,cur_cnt); cur_cnt = 1;} return cur_cnt; } public static int coordinate_exists(int x_in, int y_in, int A_x_length, int A_y_length) { if (x_in >= 0 && x_in <= (A_x_length-1) && y_in >= 0 && y_in <= (A_y_length-1)) { return 1; } else { return 0; } } }