63. Unique Paths II

#dp

Problem

Unique Paths II - LeetCodeLeetCode

Intuition

Intuition

Time Complexity

Space Complexity

Solution

class Solution {
    public int uniquePathsWithObstacles(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] dp = new int[m][n];

        return tabulationSpaceOptimisedHelper(grid);
    }

    /**
     * Calculates the number of unique paths using a tabulation (bottom-up) approach using obstalce grid itself.
     *
     * Time complexity: O(m * n), where m is the number of rows and n is the number of columns in the grid.
     * Space complexity: O(1), No extra space is used, making use of input matrix only to store calculations
    */
    public int tabulationSpaceOptimisedHelper(int[][] obstacleGrid) {
        int R = obstacleGrid.length; // Number of rows
        int C = obstacleGrid[0].length; // Number of columns
    
        // If the starting position is blocked, there are no paths possible.
        if (obstacleGrid[0][0] == 1) {
            return 0;
        }
    
        // Set the starting position as 1 to indicate that there is one path to reach it.
        obstacleGrid[0][0] = 1;
    
        // Calculate the number of paths for the first row.
        for (int col = 1; col < C; col++) {
            // If the current cell is not an obstacle and the cell on the left has a valid path, 
            // set the current cell's path count to 1.
            if (obstacleGrid[0][col] == 0 && obstacleGrid[0][col - 1] == 1) {
                obstacleGrid[0][col] = 1;
            } else {
                // Otherwise, set the current cell's path count to 0.
                obstacleGrid[0][col] = 0;
            }
        }
    
        // Calculate the number of paths for the first column.
        for (int row = 1; row < R; row++) {
            // If the current cell is not an obstacle and the cell above has a valid path, 
            // set the current cell's path count to 1.
            if (obstacleGrid[row][0] == 0 && obstacleGrid[row - 1][0] == 1) {
                obstacleGrid[row][0] = 1;
            } else {
                // Otherwise, set the current cell's path count to 0.
                obstacleGrid[row][0] = 0;
            }
        }
    
        // Calculate the number of paths for the remaining cells.
        for (int row = 1; row < R; row++) {
            for (int col = 1; col < C; col++) {
                if (obstacleGrid[row][col] == 0) {
                    // If the current cell is not an obstacle, calculate the number of paths as the sum
                    // of paths from the above cell and the left cell.
                    obstacleGrid[row][col] = obstacleGrid[row - 1][col] + obstacleGrid[row][col - 1];
                } else {
                    // If the current cell is an obstacle, set the number of paths to reach it as 0.
                    obstacleGrid[row][col] = 0;
                }
            }
        }

        // Return the number of paths to reach the bottom-right corner.
        return obstacleGrid[R - 1][C - 1];
    }


    /**
     * Calculates the number of unique paths using a tabulation (bottom-up) approach.
     *
     * Time complexity: O(m * n), where m is the number of rows and n is the number of columns in the grid.
     * Space complexity: O(m * n), for the dp array to store intermediate results.
     */
    private int tabulationHelper(int[][] grid, int[][] dp) {
        if(grid[0][0] == 1) {
            return 0;
        }

        dp[0][0] = 1;
        int R = grid.length, C = grid[0].length;

        // Calculate the number of paths for the first column
        for(int row = 1; row < R; row++) {
            if(grid[row][0] == 0 && dp[row-1][0] == 1) {
                dp[row][0] = 1;
            }
        }

        // Calculate the number of paths for the first row
        for(int col = 1; col < C; col++) {
            if(grid[0][col] == 0 && dp[0][col-1] == 1) {
                dp[0][col] = 1;
            }
        }

        // Calculate the number of paths for the remaining cells
        for(int row = 1; row < R; row++) {
            for(int col = 1; col < C; col++) {
                if(grid[row][col] == 0) {
                    int up = dp[row-1][col];
                    int left = dp[row][col-1];
                    dp[row][col] = up + left;
                }
            }
        }
        return dp[R-1][C-1];
    }

    /**
     * Calculates the number of unique paths using a memoization (top-down) approach.(TLE)
     *
     * Time complexity: O(m * n), where m is the number of rows and n is the number of columns in the grid.
     * Space complexity: O(m * n), for the dp array to store intermediate results.
     */
    private int memoizationHelper(int i, int j, int[][] grid, int[][] dp) {
        // If we go out of bounds or encounter an obstacle, return 0 as there are no paths.
        if(i < 0 || j < 0 || grid[i][j] == 1) {
            return 0;
        }

        // If we reach the top-left corner, return 1 as we have found a unique path.
        if(i == 0 && j == 0) {
            return 1;
        }

        // If the result for the current position is already computed, return it from the dp array.
        if(dp[i][j] != 0) {
            return dp[i][j];
        }

        // Calculate the number of paths by recursively moving either up or left.
        int up = memoizationHelper(i-1, j, grid, dp);
        int left = memoizationHelper(i, j-1, grid, dp);

        // Store the computed result in the dp array and return it.
        return dp[i][j] = up + left;
    }

    /**
     * Calculates the number of unique paths using a recursive approach.(TLE)
     *
     * Time complexity: O(2^(m + n)), where m is the number of rows and n is the number of columns in the grid.
     * Space complexity: O(m + n), for the recursion stack.
     */
    private int recursiveHelper(int i, int j, int[][] grid) {
        // If we reach the top-left corner, return 1 as we have found a unique path.
        if(i == 0 && j == 0) {
            return 1;
        }

        // If we go out of bounds or encounter an obstacle, return 0 as there are no paths.
        if(i < 0 || j < 0 || grid[i][j] == 1) {
            return 0;
        }

        // Calculate the number of paths by recursively moving either up or left.
        int up = recursiveHelper(i-1, j, grid);
        int left = recursiveHelper(i, j-1, grid);

        // Return the sum of paths from the current position.
        return up + left;
    }
}