© Parineeth M R
Question 59. A 2-dimensional matrix consists of 0’s and 1’s. An island is defined as a contiguous occurrence of 1’s that are adjacent to each other. Find the number of islands in the matrix
If there are two adjacent cells (left-right neighbors, top-down neighbors, diagonally adjacent neighbors) with a value 1, then the two cells belong to the same island. In the matrix below there are 3 islands. The cells A0, B1, C0, D0 and E0 form one island. The cells A3, B3, C3 and B4 form one island. The cell E3 forms the remaining island.
To find the number of islands, we make use of recursion. Once we find a cell whose value is 1, we start with the neighbors of this cell and recursively visit all cells that are reachable from this cell. To prevent from going into loops, we keep track if a cell has been visited or not and once a cell has been visited, we don’t visit it again.
A similar problem is the flood fill problem. The color at each pixel of an image is stored in a 2 dimensional matrix. Given the starting pixel and the new color, we have to change the color of all adjacent pixels that have the same color as the starting pixel. So if the starting pixel A[2][3] is red and the new color is blue, then we have to recursively find all red cells that are reachable from A[2][3] and change their color to blue.
In some cases, diagonal neighbors may not be considered as adjacent. It is better to clarify this with the interviewer.
C/C++
/*
Helper function that indicates if we can enter the cell or not
*/
int can_enter_cell(int matrix[][MAX_NUM_COLS], int is_visited[][MAX_NUM_COLS],
int cur_row, int cur_col, int n_rows, int n_cols)
{
/*If we are outside the bounds of the matrix or
if the cell is already visited or if the value in cell is 0
then we shouldn't enter the cell */
if (cur_row < 0 || cur_row >= n_rows
|| cur_col < 0 || cur_col >= n_cols
|| is_visited[cur_row][cur_col]
|| matrix[cur_row][cur_col] == 0) {
return 0;
}
return 1;
}
/* Helper function to count the number of islands of 1's
matrix: 2d matrix consisting of 0's and 1's
is_visited: if cell (i, j) has been visited, is_visited[i][j] is set to 1
cur_row: row of the current cell being processed
cur_col: column of the current cell being processed
n_rows: number of rows in the matrix
n_cols: number of columns in the matrix
*/
void expand_search(int matrix[][MAX_NUM_COLS], int is_visited[][MAX_NUM_COLS],
int cur_row, int cur_col, int n_rows, int n_cols)
{
int i, j;
is_visited[cur_row][cur_col] = 1;
/*For the current cell, find out if we can continue the island of 1's
with its neighbors. Each cell has 9 neighbors. The rows
of neighbors will vary from cur_row - 1 to cur_row + 1
The columns of the neighbors will vary from cur_col - 1
to cur_col + 1*/
for (i = -1; i <= 1; ++i) {
for (j = -1; j <= 1; ++j) {
int is_safe_cell = can_enter_cell(matrix, is_visited,
cur_row+i, cur_col+j, n_rows, n_cols);
if (is_safe_cell) {
expand_search(matrix, is_visited, cur_row+i,
cur_col+j, n_rows, n_cols);
}
}
}
}
/* Main function to find the number of islands of 1's
matrix: 2d matrix consisting of 0's and 1's. Should not be empty
n_rows: number of rows in the matrix. Should be >= 1
n_cols: number of columns in the matrix. Should be >= 1
*/
int find_islands(int matrix[][MAX_NUM_COLS], int n_rows, int n_cols)
{
int is_visited[MAX_NUM_ROWS][MAX_NUM_COLS];
int i, j, count;
/*Initially all cells are not yet visited*/
for (i = 0; i < n_rows; ++i)
for (j = 0; j < n_cols; ++j)
is_visited[i][j] = 0;
/*Search all the cells in matrix that are not yet visited*/
count = 0;
for (i = 0; i < n_rows; ++i) {
for (j = 0; j < n_cols; ++j) {
if (matrix[i][j] && !is_visited[i][j]) {
/*We have found an island. Now expand the island
in all directions*/
expand_search(matrix, is_visited, i, j,
n_rows, n_cols);
++count;
}
}
}
return count;
}
Java
/* Helper function that indicates if we can enter the cell or not*/
public static boolean canEnterCell(int[][] matrix, boolean[][] isVisited,
int curRow, int curCol) {
int nRows = matrix.length;
int nCols = matrix[0].length;
/*If we are outside the bounds of the matrix or
if the cell is already visited or if the value in cell is 0
then we shouldn't enter the cell */
if (curRow < 0 || curRow >= nRows
|| curCol < 0 || curCol >= nCols
|| isVisited[curRow][curCol]
|| matrix[curRow][curCol] == 0) {
return false;
}
return true;
}
/* Helper function to count the number of islands of 1's
matrix: 2d matrix consisting of 0's and 1's
isVisited: if cell (i, j) has been visited, isVisited[i][j] is set to true
curRow: row of the current cell being processed
curCol: column of the current cell being processed
*/
public static void expandSearch(int[][] matrix, boolean[][] isVisited, int curRow, int curCol) {
int nRows = matrix.length;
int nCols = matrix[0].length;
isVisited[curRow][curCol] = true;
/*For the current cell, find out if we can continue the island of 1's
with its neighbors. Each cell has 9 neighbors. The rows
of neighbors will vary from curRow - 1 to curRow + 1
The columns of the neighbors will vary from curCol - 1
to curCol + 1*/
for (int i = -1; i <= 1; ++i) {
for (int j = -1; j <= 1; ++j) {
boolean isSafeCell = canEnterCell(matrix, isVisited, curRow+i,
curCol+j);
if (isSafeCell) {
expandSearch(matrix, isVisited, curRow+i, curCol+j);
}
}
}
}
/* Main function to find the number of islands of 1's
matrix: 2d matrix consisting of 0's and 1's. Should not be empty
*/
public static int findIslands(int[][] matrix) {
int nRows = matrix.length;
int nCols = matrix[0].length;
boolean[][] isVisited = new boolean[nRows][nCols];
/*Initially all cells are not yet visited*/
int i, j;
for (i = 0; i < nRows; ++i)
for (j = 0; j < nCols; ++j)
isVisited[i][j] = false;
/*Search all the cells in matrix that are not yet visited*/
int count = 0;
for (i = 0; i < nRows; ++i) {
for (j = 0; j < nCols; ++j) {
if (matrix[i][j] == 1 && !isVisited[i][j]) {
/*We have found an island. Now expand the island
in all directions*/
expandSearch(matrix, isVisited, i, j);
++count;
}
}
}
return count;
}
Python
#Helper function that indicates if we can enter the cell or not def can_enter_cell(matrix, is_visited, cur_row, cur_col) : n_rows = len(matrix) n_cols = len(matrix[0]) #If we are outside the bounds of the matrix or #if the cell is already visited or if the value in cell is 0 #then we shouldn't enter the cell if (cur_row < 0 or cur_row >= n_rows or cur_col < 0 or cur_col >= n_cols or is_visited[cur_row][cur_col] or matrix[cur_row][cur_col] == 0) : return False return True #Helper function to count the number of islands of 1's #matrix: 2-D matrix consisting of 0's and 1's #is_visited: if cell (i, j) has been visited, is_visited[i][j] is set to True #cur_row: row of the current cell being processed #cur_col: column of the current cell being processed def expand_search(matrix, is_visited, cur_row, cur_col) : n_rows = len(matrix) n_cols = len(matrix[0]) is_visited[cur_row][cur_col] = True #For the current cell, find out if we can continue the island of 1's #with its neighbors. Each cell has 8 neighbors. The rows #of neighbors will vary from cur_row - 1 to cur_row + 1 #The columns of the neighbors will vary from cur_col - 1 #to cur_col + 1 for i in range(-1, 2): for j in range(-1, 2): is_safe_cell = can_enter_cell(matrix, is_visited, cur_row+i, cur_col+j) if (is_safe_cell) : expand_search(matrix, is_visited, cur_row+i, cur_col+j) #Main function to find the number of islands of 1's #matrix: 2-D matrix consisting of 0's and 1's. Should not be empty def find_islands(matrix) : n_rows = len(matrix) n_cols = len(matrix[0]) is_visited = [ [False for x in range(n_cols)] for x in range(n_rows)] #Search all the cells in matrix that are not yet visited count = 0 for i in range(0, n_rows): for j in range(0, n_cols): if (matrix[i][j] == 1 and not is_visited[i][j]) : #We have found an island. Now expand the island #in all directions expand_search(matrix, is_visited, i, j) count += 1 return count