# 63. Unique Paths II

## Problem

{% embed url="<https://leetcode.com/problems/unique-paths-ii/description/>" %}

## Intuition

It follows the same approach as [62.-finding-unique-path](https://chkrishnatej.gitbook.io/interview-prep/dynamic-programming/2d-dp/62.-finding-unique-path "mention"). The only thing is it has an extra constraint where you could be blocked from exploring in few cells.

<figure><img src="https://1388126071-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MVQ7Ie-PZpN_8yApX0-%2Fuploads%2FYyWMiZmXqfOMgg0TLXup%2Fimage.png?alt=media&#x26;token=108c8790-ef7f-4972-80f2-23d56209df76" alt=""><figcaption></figcaption></figure>

<figure><img src="https://1388126071-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MVQ7Ie-PZpN_8yApX0-%2Fuploads%2FVnurNUm4WIos0OZkgrf7%2Fimage.png?alt=media&#x26;token=e37032e7-1362-4752-919b-8f0ac1bda4a0" alt=""><figcaption></figcaption></figure>

<figure><img src="https://1388126071-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MVQ7Ie-PZpN_8yApX0-%2Fuploads%2FC0391cvDuGCasHWukyuv%2Fimage.png?alt=media&#x26;token=b448ba6e-f105-417e-8dd4-f3c8fa63928f" alt=""><figcaption></figcaption></figure>

## Solution

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

        return tabulationHelper(grid, dp);
    }

    /**
     * Calculates the number of unique paths using a tabulation (bottom-up) approach.
     */
    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++) {
            // Before we update the current dp cell, we need to check if the 
            // current cell of grid is accessible and also check if the previous 
            // cell is accessible. If the previous cell is not accessible then
            // the move cannot be made to current cell.
            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.
     * This function is not used in this code.
     */
    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.
        if(dp[i][j] != 0) {
            return dp[i][j];
        }

        // 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);

        // 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.
     */
    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;
    }
}

```