Java - O(mn) time and O(1) space - TimeLimitExceeded - Can someone please explain why?


  • 0
    B

    Hi,
    I tried to solve the problem using Depth First Search. I basically, try to find number of paths from a particular cell to destination. Could someone please tell me why this is giving a TimeLimitExceededException even though it is solving in O(mn) time?

    class Solution {
        public int uniquePathsWithObstacles(int[][] obstacleGrid) {
            if(obstacleGrid == null || obstacleGrid.length==0 || obstacleGrid[0].length==0) {
                return 0;
            }
            int rows = obstacleGrid.length;
            int cols = obstacleGrid[0].length;
            // mark all obstacles to -ve values
            for(int i=0; i<rows; i++) {
                for(int j=0; j<cols; j++) {
                    if(obstacleGrid[i][j] == 1) {
                        obstacleGrid[i][j] = -1;                
                    }
                }
            }
            return dfs(obstacleGrid, 0, 0); 
        }
    
        private int dfs(int[][] grid, int r, int c) {        
            if(r>=grid.length || c>=grid[0].length) { // out of range
                return 0;
            } else if(grid[r][c] < 0) { // obstacle
                return 0;
            } else if(grid[r][c] > 0) { // num paths from r,c to destination is already computed
                return grid[r][c];
            } else if(r == grid.length-1 && c == grid[0].length-1) { // destination
                return 1;
            }
            // need to compute num paths from current position to destination
            int paths = dfs(grid, r+1, c);
            paths += dfs(grid, r, c+1);
            grid[r][c] = paths;
            return paths;
        }
    }
    

Log in to reply
 

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