Leetcode-Depth-First Search
Reference: Link
DFS is often used to solve accessibility problem. We get a graph and try to figure out if we can arrive at the node from the start node. We use stack to achieve dfs and we also need visited array to record all visited nodes.
695. Max Area of Island (Medium)
This problem is very intuitive. We need to find all possible islands and compare their area to find the maximum area. In order to find all possible islands, we need to iterate all positions in this matrix. If grid[i][j]==1, we find a possible island and begin dfs. Dfs can help us find the area of this island. Remember if we visited a position, change its value as 0 so that we will not visit this position again.
Time complexity is O(R*C), where R is the number of rows in the given grid, and C is the number of columns. We visit every square once. Space complexity: O(1). Here is the link.
public int maxAreaOfIsland(int[][] grid) {
int ans = 0;
for(int i =0;i<grid.length;i++){
for(int j =0;j<grid[i].length;j++){
if(grid[i][j]==1){
ans = Math.max(dfs(grid,i,j),ans);
}
}
}
return ans;
}
public int dfs(int[][]grid,int i, int j){
int ans = 1;
grid[i][j]=0;
int[][] directions = {{0,1},{1,0},{0,-1},{-1,0}};
for(int []direct:directions){
int newposx = direct[0]+i;
int newposy = direct[1]+j;
if(newposx>=0 && newposx<grid.length && newposy >=0 && newposy < grid[0].length && grid[newposx][newposy]==1)
ans+=dfs(grid,newposx,newposy);
}
return ans;
}
200. Number of Islands (Medium)
This problem is similar to the last problem. In the last problem, we need to find the maximum area. In this problem, we need to find the number of island. We just need to return different value.
Time complexity is O(R*C), where R is the number of rows in the given grid, and C is the number of columns. We visit every square once. Space complexity: O(1). Here is the link.
public int numIslands(char[][] grid) {
int ans = 0;
for(int i =0;i<grid.length;i++){
for(int j =0;j<grid[i].length;j++){
if(grid[i][j]=='1'){
island(grid,i,j);
ans++;
}
}
}
return ans;
}
public void island(char[][] grid,int i, int j){
if(i<0||j<0||i>=grid.length||j>=grid[0].length||grid[i][j]=='0')return;
grid[i][j]='0';
int[][] directions = {{0,1},{1,0},{-1,0},{0,-1}};
for(int[]direct:directions){
int newx = i + direct[0];
int newy = j + direct[1];
island(grid,newx,newy);
}
}
547. Friend Circles (Medium)
We can transform friend circle to a graph. If A is a direct friend of B, A node and B node has an edge. If A is an indirect friend of C, A and C can be connected indirectly in the graph. Therefore, we need to use dfs to find all possible connections as friend circles. And we record all friends that we have iterated.
Time complexity is O(n^2). Space complexity is O(n). Here is the link.
public int findCircleNum(int[][] M) {
if(M.length==0)return 0;
int ans = 0;
HashSet<Integer>visited = new HashSet();
for(int i =0;i<M.length;i++){
if(visited.contains(i))continue;
dfs(M,i,visited);
ans++;
}
return ans;
}
public void dfs(int[][]M, int friend,HashSet<Integer>visited){
int []direct = M[friend];
visited.add(friend);
for(int i =0;i<M.length;i++){
if(visited.contains(i)||M[friend][i]==0)continue;
dfs(M,i,visited);
}
}
130. Surrounded Regions (Medium)
Another graph problem. In this problem, we need to deal with letter ‘O’ on the border. We need to distinguish letter ‘O’ on the border and not on the border. The best way is to change letter ‘O’ on the border to another letter. I changed it to letter ‘.'. And I use dfs to search all letter ‘O’ which are connected with letter ‘O’ on the border. Change them to letter ‘.'. Then, I iterate all regions in 2D board. If it’s letter ‘.', restore it to letter ‘O’. If it’s letter ‘O’, change it to letter ‘X’.
Time complexity is O(mn). Space complexity is O(1). mn is the size of board. Here is the link.
public void solve(char[][] board) {
if(board.length==0||board[0].length==0)return;
for(int i =0;i<board.length;i++){
for(int j =0;j<board[i].length;j++){
if(board[i][j]=='O' &&(i==0||i==board.length-1||j==0||j==board[i].length-1))
dfs(board,i,j);
}
}
for(int i =0;i<board.length;i++){
for(int j =0;j<board[i].length;j++){
if(board[i][j]=='.')
board[i][j]='O';
else if(board[i][j]=='O')
board[i][j]='X';
}
}
}
public void dfs(char[][]board, int i, int j){
if(i<0||i>=board.length||j<0||j>=board[i].length||board[i][j]=='X'||board[i][j]=='.')return;
int[][] directions = {{0,1},{1,0},{-1,0},{0,-1}};
board[i][j]= '.';
for(int[] direct:directions){
int newposx = i+direct[0];
int newposy = j +direct[1];
dfs(board,newposx,newposy);
}
}
417. Pacific Atlantic Water Flow (Medium)
I designed two solutions to solve this problem. Both solutions use dfs. One solution starts dfs from each cell. The other solution starts dfs from the border.
The first solution is we use dfs for each cell to check whether water starts from this cell can touch both oceans. We still need a set to record visited cells. And we need to clear this set in each dfs, because we use dfs starts from the different cells and want to go to different oceans. We can use two hashmaps to replace with visited hashset. The key is the position of the cell. The value is a boolean variable means if we can reach Pacific/Atlantic. This can help us reduce running time. When we are using dfs, we need to check whether current position is on the border. If it’s on the border, this means the path can reach one ocean.
public List<List<Integer>> pacificAtlantic(int[][] matrix) {
List<List<Integer>> ans = new ArrayList();
HashSet<List<Integer>>visited = new HashSet();
for(int i =0;i<matrix.length;i++){
for(int j =0;j<matrix[i].length;j++){
visited = new HashSet();
if(dfs(matrix,i,j,0,visited)){
visited = new HashSet();
if(dfs(matrix,i,j,1,visited))
ans.add(new ArrayList(Arrays.asList(i,j)));
}
}
}
return ans;
}
public boolean dfs(int[][] matrix, int i,int j, int atlan, HashSet<List<Integer>>visited){
List<Integer>pos = new ArrayList();
pos.add(i);
pos.add(j);
visited.add(pos);
int bordertop = atlan== 0?0:matrix.length-1;
int borderleft = atlan == 0? 0:matrix[0].length-1;
if(i==bordertop || j == borderleft)return true;
int[][] directions = {{0,1},{1,0},{0,-1},{-1,0}};
for(int []direct:directions){
int newx = i + direct[0];
int newy = j + direct[1];
List<Integer>newpos = new ArrayList();
newpos.add(newx);
newpos.add(newy);
if(newx<0||newy<0||newx>=matrix.length||newy>=matrix[0].length||visited.contains(newpos)||matrix[newx][newy]>matrix[i][j])
continue;
if(dfs(matrix,newx,newy,atlan,visited))
return true;
}
return false;
}
The second solution reduces running time and memory. We use dfs for each cell on the border. If a cell is connected with the cell on the border, we set this cell as true. And we need to build 2 arrays for pacific and atlantic separately. At last, we iterate these two arrays. If a cell is true for both pacific and atlantic, this cell is one of our answers.
public List<List<Integer>> pacificAtlantic(int[][] matrix) {
List<List<Integer>> ans = new ArrayList();
if(matrix.length==0||matrix[0].length==0)return ans;
int m = matrix.length;
int n = matrix[0].length;
boolean [][]pacific = new boolean[m][n];
boolean [][]atlantic = new boolean[m][n];
for(int i =0;i<m;i++){
dfs(matrix,pacific,-1,i,0);
dfs(matrix,atlantic,-1,i,n-1);
}
for(int i=0;i<n;i++){
dfs(matrix,pacific,-1,0,i);
dfs(matrix,atlantic,-1,m-1,i);
}
for(int i =0;i<m;i++){
for(int j =0;j<n;j++){
if(pacific[i][j]&&atlantic[i][j]){
ans.add(new ArrayList(Arrays.asList(i,j)));
}
}
}
return ans;
}
public void dfs(int[][] matrix, boolean[][]ocean,int pre, int i,int j){
int m = matrix.length, n = matrix[0].length;
if (i < 0 || i >= m || j < 0 || j >= n || ocean[i][j] || matrix[i][j] < pre) return;
ocean[i][j] = true;
dfs(matrix, ocean, matrix[i][j], i + 1, j);
dfs(matrix, ocean, matrix[i][j], i - 1, j);
dfs(matrix, ocean, matrix[i][j], i, j + 1);
dfs(matrix, ocean, matrix[i][j], i, j - 1);
}
Time complexity is O(mn). mn is the size of matrix. Space complexity is O(mn). Here is the link.