Depth first search (DFS) is an algorithm to traverse each element in the data structure. It starts from the source node, which can be root of the tree, or the start of the string, or a cell in matrix. We visit its adjacent node (or children) down the path before visit its other adjacent notes. DFS can be applied to string operations, tree, graph and adjacent matrix. In this post, we focus on depth first search and adjacent matrix only. Adjacent matrix is one representation of graph. Many problem in adjacent matrix uses DFS to solve.
Two examples are introduced to demonstrate depth first search and adjacent matrix: Number of islands and Max region. In both problems, the matrix is a binary matrix with 0s or 1s. The island consists of 1s surrounded by 0s. Number of islands is to count the number of islands in matrix. Sometimes the question is also called “number of shape”. Max Region is to find the islands that has the most count of 1s.
Normally, there are two ways to implement DFS – recursion and stack. In this implementation, we use recursion. There are two methods, wrapper method and helper method. Wrapper method declares variables and call helper method. The helper method is a recursion function. First it checks whether the termination condition is met. Next it checks whether the answer can be found in the pre-defined variables, such as visited. If found, which indicates the node has been visited, we can skip. If not, visit it. Then call itself to visit its 4 (or 8) neighbors.
1. Number of Islands
Facebook Interview Question (CareerCup):
Given a 2d array of 0s and 1s, 0 means water, 1 means land, connected 1s form an island, count the number of islands on this map.
{0, 1, 0, 1, 0}
{0, 1, 0, 0, 1}
{0, 1, 1, 0, 1}
returns 3
Java Code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
public class NumOfIslands { //DFS wrapper, Time O(m*n), Space O(m*n), m is number of rows, n is number of columns public static int numOfIslands(int[][] mat) { int m = mat.length, n = mat[0].length; if (mat == null || m == 0 || n == 0) return 0; int count = 0; boolean[][] visited = new boolean[m][n]; //as memo for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (mat[i][j] == 1) { count++; dfs(mat, i, j, visited); } } } return count; } //DFS + memoization, Time O(4) ~ O(1), Space O(1), 4 directions is constant private static void dfs(int[][] mat, int i, int j, boolean[][] visited) { int m = mat.length, n = mat[0].length; if (i < 0 || j < 0 || i > m-1 || j > n-1 || visited[i][j]) return; if (mat[i][j] != 1) return; mat[i][j] = 0; visited[i][j] = true; dfs(mat, i-1, j, visited); //left dfs(mat, i+1, j, visited); //right dfs(mat, i, j-1, visited); //upper dfs(mat, i, j+1, visited); //lower } public static void main(String args[]) { int[][] matrix = {{0,1,0,1,0}, {0,1,0,0,1}, {0,1,1,0,1} }; System.out.println("number of islands: " + numOfIslands(matrix)); } } |
Output:
number of islands: 3
O Notation:
Time complexity: O(m*n)
Space complexity: O(m*n)
m is number of rows, n is number of columns
2. Max Region
Goolge Interview Question:
Consider a matrix where each cell contains either a 0 or a 1 and any cell containing a 1 is called a filled cell.
Two cells are said to be connected if they are adjacent to each other horizontally, vertically, or diagonally.
Given a matrix, find the number of cells in the largest region in the matrix.
Example:
{1, 1, 0, 0},
{0, 1, 1, 0},
{0, 0, 1, 0},
{1, 0, 0, 0}
Output: 5
Java Code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
public class MaxRegion { //DFS wrapper, Time O(m*n), Space O(m*n), m is number of rows, n is number of columns public static int maxRegion(int[][] mat) { int max = 0; for (int i = 0; i < mat.length; i++) { for (int j = 0; j < mat[0].length; j++) { max = Math.max(max, dfs(mat, i, j)); } } return max; } //DFS + memorization, Time O(8) ~ O(1), Space O(1), 8 directions are constant private static int dfs(int[][]mat, int x, int y) { if (x < 0 || y < 0|| x >= mat.length || y >= mat[0].length || mat[x][y] == 0) return 0; int count = mat[x][y]--; //change matrix value to track visited status for (int i = x-1; i < x+2; i++) //8 directions for (int j = y-1; j < y+2; j++) count += dfs(mat, i, j); return count; } public static void main(String[] args){ int[][] matrix = {{1,1,0,0}, {0,1,1,0}, {0,0,1,0}, {1,0,0,0}}; System.out.println("The number of cells in max region is: "+ maxRegion(matrix)); } } |
Output:
The number of cells in max region is: 5
O Notation:
Time complexity: O(m*n)
Space complexity: O(m*n)
Download DFSAdjacentMatrix.zip
Big O-Notations of DFS and BFS
Shortest path between cells in matrix BFS
