Short DP Solution in JAVA with O(n) space


  • 0
    I
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
            int n = obstacleGrid.length;
            int m = obstacleGrid[0].length;
            int ways[] = new int[m];
            ways[0] = (obstacleGrid[0][0] == 1) ? 0 : 1;
    
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (j < m - 1) {
                        ways[j + 1] += obstacleGrid[i][j + 1] == 1 ? 0 : ways[j];
                    }
                    if (i < n - 1 && obstacleGrid[i + 1][j] == 1) {
                        ways[j] = 0;
                    }
                }
            }
    
            return ways[m - 1];
        }
    

Log in to reply
 

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