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
|
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)); } } |
JavaScript
|
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 |
class NumOfInlands { //DFS wrapper, Time O(m*n), Space O(m*n), m is number of rows, n is number of columns numOfIslands(mat) { var m = mat.length, n = mat[0].length; if (mat == null || m == 0 || n == 0) return 0; var count = 0; var visited = []; //as memo for (let i = 0; i < m; i++) { visited[i] = new Array(n); } for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { if (mat[i][j] == 1) { count++; this.dfs(mat, i, j, visited); } } } return count; } //DFS + memoization, Time O(4) ~ O(1), Space O(1), 4 directions is constant dfs(mat, i, j, visited) { var 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; this.dfs(mat, i-1, j, visited); //left this.dfs(mat, i+1, j, visited); //right this.dfs(mat, i, j-1, visited); //upper this.dfs(mat, i, j+1, visited); //lower } } const matrix = [[0,1,0,1,0], [0,1,0,0,1], [0,1,1,0,1]]; var n = new NumOfInlands(); console.log("number of islands: " + n.numOfIslands(matrix)); |
Python
|
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 |
class NumOfInslands: #DFS wrapper, Time O(m*n), Space O(m*n), m is number of rows, n is number of columns def numOfIslands(self, mat) : m = len(mat) n = len(mat[0]) if mat == None or m == 0 or n == 0: return 0 count = 0; visited = [[False for i in range(n)] for j in range(m)] for i in range(0, m): for j in range (0, n): if mat[i][j] == 1: count+=1 self.dfs(mat, i, j, visited) return count #DFS + memoization, Time O(4) ~ O(1), Space O(1), 4 directions is constant def dfs(self, mat, i, j, visited) : m = len(mat) n = len(mat[0]) if i < 0 or j < 0 or i > m-1 or j > n-1 or visited[i][j]: return if mat[i][j] != 1: return mat[i][j] = 0 visited[i][j] = True self.dfs(mat, i-1, j, visited); #left self.dfs(mat, i+1, j, visited); #right self.dfs(mat, i, j-1, visited); #upper self.dfs(mat, i, j+1, visited); #lower matrix = [[0,1,0,1,0], [0,1,0,0,1], [0,1,1,0,1]] n = NumOfInslands() print("number of islands: " + str(n.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
|
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 |
public class MaxRegion { private static int count = 0; //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 m = mat.length, n = mat[0].length; if (mat == null || m == 0 || n == 0) return 0; boolean[][] visited = new boolean[m][n]; int largest = 0; for (int i = 0; i < m; i++){ for (int j = 0; j < n; j++){ if (mat[i][j] == 1 && !visited[i][j]){ dfs(mat,i, j, visited); largest = Math.max(largest, count); count = 0; } } } return largest; } //DFS + memoization, Time O(8) ~ O(1), Space O(1), 8 directions is constant private static void dfs(int[][]mat, int x, int y,boolean[][] visited) { int m = mat.length, n = mat[0].length; if(x < 0 || y < 0 || x >= m || y >= n || mat[x][y] == 0 || visited[x][y]) return ; visited[x][y] = true; count++; for (int i = x-1; i < x+2; i++) //check all 8 directions for (int j = y-1; j < y+2; j++) dfs(mat, i, j, visited); } 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)); } } |
JavaScript
|
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 45 46 47 48 |
class maxRegion { //Constructor, Time O(1) Space O(1) constructor () { this.count = 0; } //DFS wrapper, Time O(m*n), Space O(m*n), m is number of rows, n is number of columns maxRegion(matrix) { var m = matrix.length, n = matrix[0].length; if (matrix == null || m == 0 || n == 0) return 0; var visited = []; //as memo for (let i = 0; i < m; i++) { visited[i] = new Array(n); } var largest = 0; for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { if (matrix[i][j] == 1 && !visited[i][j]){ this.dfs(matrix, i, j, visited); largest = Math.max(largest, this.count); this.count = 0; } } } return largest; } //DFS + memoization, Time O(8) ~ O(1), Space O(1), 8 directions is constant dfs( matrix, x, y, visited){ var m = matrix.length, n = matrix[0].length; if (x < 0 || y < 0|| x >= m || y >= n || matrix[x][y] == 0 || visited[x][y]) return ; visited[x][y] = true; this.count++; for(let i = x-1; i < x+2; i++) //check all 8 directions for(let j = y-1; j < y+2; j++) this.dfs(matrix, i, j, visited); } } const matrix = [[1,1,0,0], [0,1,1,0], [0,0,1,0], [1,0,0,0]]; var m = new maxRegion(); console.log("The number of cells in max region is: " + m.maxRegion(matrix)); |
Python
|
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 |
class MaxRegion : #Constructor, Time O(1) Space O(1) def __init__(self) : self.count = 0 # DFS wrapper, Time O(m*n), Space O(m*n), m is number of rows, n is number of columns def maxRegion(self, matrix): m = len(matrix) n = len(matrix[0]) if matrix == None or m == 0 or n == 0: return 0 visited = [[False for i in range(n)] for j in range(m)] largest = 0 for i in range(0, m): for j in range(0, n): if matrix[i][j] == 1 and visited[i][j] == False: self.dfs(matrix, i, j, visited) largest = max(largest, self.count) self.count = 0 return largest # DFS + memoization, Time O(8) ~ O(1), Space O(1), 8 directions is constant def dfs(self, matrix, x, y, visited): m = len(matrix) n = len(matrix[0]) if x<0 or y<0 or x>= m or y >= n or matrix[x][y] == 0 or visited[x][y] == True: return visited[x][y] = True self.count += 1 for i in range(x-1, x+2): #8 directions for j in range(y-1, y+2): self.dfs(matrix, i, j, visited) matrix = [[1,1,0,0], [0,1,1,0], [0,0,1,0], [1,0,0,0]] m = MaxRegion() print("The number of cells in max region is: "+ str(m.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 NumOfInslands.zip
Download MaxRegion.zip
Big O-Notations of DFS and BFS
Shortest path between cells in matrix BFS
Adjacency matrix implementation
