## Find the number of islands in a matrix

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

```

I hope you liked the article. I have written “The Big Book of Coding Interviews” in C/C++, Java and Python. If you are a US resident and want a free copy of the book, please send an email to

Mention the programming language of your choice in the e-mail. I will mail the Amazon Giveaway link to you. If you like the book please give your review comments on Amazon. If you didn’t like the book, please mail me what you didn’t like and I will be glad to make the required changes.

## Sudoku solver

Question 58. Implement a Sudoku solver

The Sudoku grid is square of size 9 * 9. The rules of Sudoku are as follows:

1. Each cell contains a number from 1 to 9

2. A number should not be repeated in the same row or the same column

3. The grid is further sub-divided into squares of 3*3 called boxes. A number should also not be repeated in the same box.

In the Sudoku puzzle, the puzzle writer fills up some of the cells with numbers and we have to fill up the remaining cells. To solve Sudoku, we make use of recursion and back-tracking. Given a cell, we recursively try out all possible numbers that can be filled up in the cell. So we fill a cell with a possible number and then move to the next cell. Suppose we hit a dead-end at a cell and can’t fill it with any number, then we back-track to the previous cell, try out the next possible number in the previous cell and proceed. To distinguish between the cells filled up by the puzzle writer and the other cells, we initialize the other cells with -1.

## C/C++

```
/* Helper function which checks if it is possible to place a number in a cell
grid: the 2d sudoku matrix
row_nr: row number of the cell we are checking
col_nr: column number of the cell we are checking
num: the number which we want to place in the cell
Returns: 1 if we can place num in the cell, 0 otherwise
*/
int can_fill_cell(int grid[][NUM_COLS], int row_nr, int col_nr, int num)
{
int i, j;
int region_start_row, region_start_col;

/*Ensure that the number is not present in any row of requested column*/
for (i = 0; i < NUM_ROWS; ++i)
if (grid[i][col_nr] == num)
return 0;

/*Ensure that the number is not present in any column of requested row*/
for (j = 0; j < NUM_COLS; ++j)
if (grid[row_nr][j] == num)
return 0;

/*Ensure that the number is not present in the 3*3 box it belongs to*/
region_start_row = (row_nr / 3) * 3;
region_start_col = (col_nr / 3) * 3;

for (i = region_start_row; i < region_start_row + 3; ++i)
for (j = region_start_col; j < region_start_col + 3; ++j)
if (grid[i][j] == num)
return 0;

return 1;
}

/*Main function for solving the sudoku puzzle
grid: the 2d sudoku matrix
row_nr: row number of the current cell being processed
col_nr: column number of the current cell being processed
*/
void solve_sudoku(int grid[][NUM_COLS], int row_nr, int col_nr)
{
int next_row, next_col, num;

if (row_nr >= NUM_ROWS) {
/*We have found a solution. print the grid and
terminate the recursion*/
print_grid(grid, 1);
return;
}

/*Pre-compute the row and column of the next cell*/
next_row = row_nr;
next_col = col_nr + 1;
if (next_col >= NUM_COLS) {
next_col = 0;
next_row = row_nr + 1;
}

if (grid[row_nr][col_nr] == -1) {
/*The puzzle writer has not assigned a number to this cell.
So try assigning numbers 1-9 to the cell*/
for (num = 1; num <= 9; ++num) {
if (can_fill_cell(grid, row_nr, col_nr, num)) {
grid[row_nr][col_nr] = num;
solve_sudoku(grid, next_row, next_col);
}
}
/*Once we are done trying all numbers from 1-9 assign the cell
back to -1 to indicate puzzle writer has not assigned a number
to the cell*/
grid[row_nr][col_nr] = -1;

} else {
/*The puzzle writer has already assigned a value to the cell.
So proceed to the next cell*/
solve_sudoku(grid, next_row, next_col);
}
}

```

## Java

```
/* Helper function which checks if it is possible to place a number in a cell
grid: the 2d sudoku matrix
rowNr: row number of the cell we are checking
colNr: column number of the cell we are checking
num: the number which we want to place in the cell
Returns: true if we can place num in the cell, false otherwise
*/
public static boolean canFillCell(int[][] grid, int rowNr, int colNr, int num) {

/*Ensure that the number is not present in any row of requested column*/
int i, j;
for (i = 0; i < NUM_ROWS; ++i)
if (grid[i][colNr] == num)
return false;

/*Ensure that the number is not present in any column of requested row*/
for (j = 0; j < NUM_COLS; ++j)
if (grid[rowNr][j] == num)
return false;

/*Ensure that the number is not present in the 3*3 box it belongs to*/
int regionStartRow = (rowNr / 3) * 3;
int regionStartCol = (colNr / 3) * 3;

for (i = regionStartRow; i < regionStartRow + 3; ++i)
for (j = regionStartCol; j < regionStartCol + 3; ++j)
if (grid[i][j] == num)
return false;

return true;
}

/*Main function for solving the sudoku puzzle
grid: the 2d sudoku matrix
rowNr: row number of the current cell being processed
colNr: column number of the current cell being processed
*/
public static void solveSudoku(int[][] grid, int rowNr, int colNr) {

if (rowNr >= NUM_ROWS) {
/*We have found a solution. print the grid and
terminate the recursion*/
printGrid(grid, true);
return;
}

/*Pre-compute the row and column of the next cell*/
int nextRow = rowNr;
int nextCol = colNr + 1;
if (nextCol >= NUM_COLS) {
nextCol = 0;
nextRow = rowNr + 1;
}

if (grid[rowNr][colNr] == -1) {
/*The puzzle writer has not assigned a number to this cell.
So try assigning numbers 1-9 to the cell*/
for (int num = 1; num <= 9; ++num) {
if (canFillCell(grid, rowNr, colNr, num)) {
grid[rowNr][colNr] = num;
solveSudoku(grid, nextRow, nextCol);
}
}
/*Once we are done trying all numbers from 1-9 assign the cell
back to -1 to indicate puzzle writer has not assigned a number
to the cell*/
grid[rowNr][colNr] = -1;

} else {
/*The puzzle writer has already assigned a value to the cell.
So proceed to the next cell*/
solveSudoku(grid, nextRow, nextCol);
}
}

```

## Python

```
#Helper function which checks if it is possible to place a number in a cell
#grid: the 2-D sudoku matrix
#row_nr: row number of the cell we are checking
#col_nr: column number of the cell we are checking
#num: the number which we want to place in the cell
#Returns: True if we can place num in the cell, False otherwise
def can_fill_cell(grid, row_nr, col_nr, num) :
#Ensure that the number is not present in any row of requested column
for  i in range(0, NUM_ROWS):
if (grid[i][col_nr] == num):
return False

#Ensure that the number is not present in any column of requested row
for  j in range(0, NUM_COLS):
if (grid[row_nr][j] == num):
return False

#Ensure that the number is not present in the 3*3 box it belongs to
region_start_row = (row_nr // 3) * 3
region_start_col = (col_nr // 3) * 3

for  i in range(region_start_row, region_start_row + 3):
for  j in range(region_start_col, region_start_col + 3):
if (grid[i][j] == num):
return False

return True

#Main function for solving the sudoku puzzle
#grid: the 2-D sudoku matrix
#row_nr: row number of the current cell being processed
#col_nr: column number of the current cell being processed
def solve_sudoku(grid, row_nr, col_nr) :
if (row_nr >= NUM_ROWS) :
#We have found a solution. print the grid and
#terminate the recursion
print_grid(grid, True)
return

#Pre-compute the row and column of the next cell
next_row = row_nr
next_col = col_nr + 1
if (next_col >= NUM_COLS) :
next_col = 0
next_row = row_nr + 1

if (grid[row_nr][col_nr] == -1) :
#The puzzle writer has not assigned a number to this cell.
#So try assigning numbers 1-9 to the cell
for  num in range(1, 10):
if (can_fill_cell(grid, row_nr, col_nr, num)) :
grid[row_nr][col_nr] = num
solve_sudoku(grid, next_row, next_col)

#Once we are done trying all numbers from 1-9, assign the cell
#back to -1 to indicate puzzle writer has not assigned a number
#to the cell
grid[row_nr][col_nr] = -1

else :
#The puzzle writer has already assigned a value to the cell.
#So proceed to the next cell
solve_sudoku(grid, next_row, next_col)

```

I hope you liked the article. I have written “The Big Book of Coding Interviews” in C/C++, Java and Python. If you are a US resident and want a free copy of the book, please send an email to

Mention the programming language of your choice in the e-mail. I will mail the Amazon Giveaway link to you. If you like the book please give your review comments on Amazon. If you didn’t like the book, please mail me what you didn’t like and I will be glad to make the required changes.

/