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

• 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;
}
}
``````

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