# Interview Questions

# Islands in a two dimensional array

- January 31, 2013
- Posted by: Kamal Rawat
- Category: Algorithms

Each element in the array is connected to eight other elements (toward top, down, left and right). For example, the zero below is connected to all the ones

1 1 1 1 0 1 1 1 1

Given a two-dimensional array of 0’s and 1’s. Find the number of islands where an island is a group of connected 1’s. For example: The below array has 4 islands (shown in different colours)

1 1 0 0 0 0 1 0 0 1 1 0 0 1 1 0 0 0 0 0 1 1 1 0 1

Write code which will accept this 2-dim array and return the number of islands.

**Solution:**

The problem is similar to the problem of connected components in graph.

The solution is simple. Look for 1 in the array which is not connected to any other graph, when you find 1 search for the all the entries in this island by recursively searching the eight connected nodes, and mark them connected.

In the code let us set the value to -1 to indicate that the node is already connected to an island.

Let’s first write the recursive function to mark the elements as connected. It will take a position (i,j) and mark it -1 and then look for nearby cells and mark all the nodes that are 1 as -1. And also call the function recursively.

void markIsland(int arr[][5], int i, int j, int m, int n) { arr[i][j] = -1; if(i-1 >= 0) { // (i-1, j-1) if(j-1 >= 0 && arr[i-1][j-1] == 1) markIsland(arr, i-1, j-1, m, n); // (i-1, j) if(arr[i-1][j] == 1) markIsland(arr, i-1, j, m, n); // (i-1, j+1) if(j+1 < n && arr[i-1][j+1] == 1) markIsland(arr, i-1, j+1, m, n); } if(i+1 < m) { // (i+1, j-1) if(j-1 >= 0 && arr[i+1][j-1] == 1) markIsland(arr, i+1, j-1, m, n); // (i+1, j) if(arr[i+1][j] == 1) markIsland(arr, i+1, j, m, n); // (i+1, j+1) if(j+1 < n && arr[i+1][j+1] == 1) markIsland(arr, i+1, j+1, m, n); } // (i, j-1) if(j-1 >= 0 && arr[i][j-1] == 1) markIsland(arr, i, j-1, m, n); // (i, j+1) if(j+1 < n && arr[i][j+1] == 1) markIsland(arr, i, j+1, m, n); }

The main function that count the islands will just call this function to mark all the elements in the islands whenever a 1 is encountered.

int countIslands(int arr[][5], int m, int n) { int count = 0; for(int i=0; i<m; i++) for(int j=0; j<n; j++) if(arr[i][j] == 1) { count++; markIsland(arr, i, j, m, n); } return count; }

The only problem with above code is that it changes all the 1’s to -1. But that can easily be corrected by adding one more loop to the function

for(int i=0; i<m; i++) for(int j=0; j<n; j++) if(arr[i][j] == -1) arr[i][j] = 1;

Time complexity: O(M*N).

Extra space will be used because of recursion.

Thank you so much for the code. The logic is very lucid and effective. Beautifully done. ðŸ˜€

Thank you! but i want a C program that display a snail by the arrangement of numbers. like:-7 8 9

6 1 2

5 4 3

My program is compiling but i cannot got the accourate result because i think so there is some mistake for returining the function value,Please correct it and send back to me.

#include

#include

#include

#include

#include

#define ROW 10

#define COL 10

int markIsland(int M[][COL], int i, int j, int m, int n);

int countIslands(int M[][COL], int m, int n);

int markIsland(int M[][COL], int i, int j, int m, int n)

{

M[i][j] = -1;

if(i-1 >= 0)

{

if(j-1 >= 0 && M[i-1][j-1] == 1)

markIsland(M, i-1, j-1, m, n);

if(M[i-1][j] == 1)

markIsland(M, i-1, j, m, n);

if(j+1 < n && M[i-1][j+1] == 1)

markIsland(M, i-1, j+1, m, n);

}

if(i+1 = 0 && M[i+1][j-1] == 1)

markIsland(M, i+1, j-1, m, n);

if(M[i+1][j] == 1)

markIsland(M, i+1, j, m, n);

if(j+1 = 0 && M[i][j-1] == 1)

markIsland(M, i, j-1, m, n);

if(j+1 < n && M[i][j+1] == 1)

markIsland(M, i, j+1, m, n);

}

int countIslands(int M[][COL], int m, int n)

{

int count = 0;

for(int i=0; i<m; i++)

for(int j=0; j<n; j++)

if(M[i][j] == -1)

M[i][j] = 1;

{

count++;

}

return count;

}

int main()

{

int m, i,j,n, c, d,f, matrix[10][10];

m = ROW;

n = COL;

srand(time(NULL));

printf("Enter the number of rows and columns of matrix\n ");

for( i = 0 ; i < m ; i++ )

{

for( j = 0 ; j < n ; j++ )

{

printf("%d\t",rand() % 2);

}

}

printf("Number of islands is: %d ", countIslands(matrix, m, n));

getch();

}