063.Unique Paths2

Posted on | In

Test cases

1
2
3
4
[[0,0]]
[[0,0,0],[0,1,0],[0,0,0]]
[[0,0,0,0],[0,1,0,0],[0,0,0,1],[0,0,0,0]]
[[0,0,0,0],[0,1,0,0],[0,0,0,1],[0,0,0,1]]

Solution 1: accepted 2ms

DP: do we really need to create another grid? Nope.
Time: O(mn)
Space: O(2mn) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    if (obstacleGrid[0][0] == 1) return 0;
    int m = obstacleGrid[0].length;
    int n = obstacleGrid.length;
    int[][] dp = new int[m][n];
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < n; j++) {
            if(i==0 && j == 0) { 
                dp[i][i] = 1;
            }
            else {
                if (obstacleGrid[j][i] == 1)
                    dp[i][j] = 0;
                else 
                    dp[i][j] = dp[Math.max(0, i-1)][j] + dp[i][Math.max(0, j-1)];
            }
        }
    }
    return dp[m-1][n-1];
}

Solution 2: accepted 2ms

Time: O(mn)
Space: O(mn) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int uniquePathsWithObstacles(int[][] input) {
    if (input[0][0] == 1) return 0;
    int m = input[0].length;
    int n = input.length;
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < n; j++) {
            if(i == 0 && j == 0) 
                input[j][i] = 1;
            else
                input[j][i] = (input[j][i] == 1)? 0 : input[Math.max(0, j-1)][i] + input[j][Math.max(0, i-1)];
        }
    }
    return input[n-1][m-1];
}