Java DFS solution, could anyone tell me how to calculate the time complexity?


  • 2

    The idea is straight forward, start from start point, go through four directions, once we meet destination return true. else return false. I use a memo matrix to store temporary result.

    public class Solution {
        
        int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
        public boolean hasPath(int[][] maze, int[] start, int[] destination) {
            if(maze.length ==0){
                return false;
            }
            if(maze[start[0]][start[1]] == 1 || maze[destination[0]][destination[1]] ==1){
                return false;
            }
            
            int row = maze.length;
            int col = maze[0].length;
            Boolean[][] memo = new Boolean[row][col];
            return helper(maze, memo, start[0], start[1], destination[0], destination[1], row, col);
            
        }
        
        
        public boolean helper(int[][] maze, Boolean[][] memo, int si, int sj, int di, int dj, int row, int col){
            if(si == di && sj == dj){
                return true;
            }
            
            if(memo[si][sj] != null){
                return memo[si][sj];
            }
            
            maze[si][sj] = -1; // mark as visited.
            
            boolean res = false;
            for(int[] dir : dirs){
                // until we reach the edge or wall;
                
                int x = si;
                int y = sj;
                
                while(x+dir[0] >=0 && x+dir[0] < row && y+dir[1] >=0 && y+dir[1] < col && maze[x+dir[0]][y+dir[1]] != 1){
                    x+=dir[0];
                    y+=dir[1];
                }
                
                //so that x,y is the next point in this direction;
                
                if(maze[x][y] != -1){
                    res |=helper(maze, memo, x, y, di, dj, row, col);
                }
            }
            
            maze[si][sj] = 0;
            memo[si][sj] = res;
            
            return res;
        }
    }
    ```
    
    Not quite sure of the time complexity. Could anybody help me with this? 
    
    Thanks.

  • 2

    Assuming there are m*n = N total elements in the matrix. The Time complexity of most DFS or BFS is O(N). The reason for this is as long as you're maintaining a visited Node array and not returning to a previously travelled path, you visit each element just once. So the complexity for the above problem solution with BFS/DFS is O(N).


  • 0
    Z

    @vishnukool Please correct me if I am wrong. Suppose the maze has size m * n. For each cell we visit, are we going to "roll" till we hit the wall, then possibly call another dfs recursive call? When we roll to one direction, the time complexity is O(max(m, n)). So for each dfs recursive call the time complexity is O(max(m, n)) and we have O(m * n) recursive calls, thus the total time complexity would be O(max(m, n) * m * n)? I think this is different than the traditional dfs because in traditional dfs each recursive call is O(1).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.