Unique Paths

find all the unique path to reach the end of matrix

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 109.

Example 1:

Input: m = 3, n = 7 Output: 28 Example 2:

Input: m = 3, n = 2 Output: 3 Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:

1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down

Constraints:

1 <= m, n <= 100

Solution

we'll start from last and if we reach at start we'll return 1 if we out of bound then we'll return 0, to find all the possible ways we'll move up and left Brute Force

var uniquePaths = function(m, n) {
    function recurr(i,j){
        if(i==0 && j==0){
            return 1
        }

        if(i<0 || j<0){
            return 0;
        }

        let up= recurr(i-1,j);
        let right= recurr(i,j-1);

        return left+up;
    }

   return recurr(m-1,n-1)
};

momorization

var uniquePaths = function (m, n) {
    let memo = Array.from({length:m} ,()=>Array(n).fill(-1))

    function recurr(i, j, memo) {
        if (i == 0 && j == 0) {
            return memo[i][j] = 1
        }

        if (i < 0 || j < 0) {
            return 0;
        }

        if (memo[i][j] !== -1) {
            return memo[i][j]
        }

        let left = recurr(i - 1, j, memo);
        let right = recurr(i, j - 1, memo);

        memo[i][j] = left + right;

        return memo[i][j];
    }

    return recurr(m - 1, n - 1, memo)
};

Tabulation

var uniquePaths = function (m, n) {
    let memo = Array.from({ length: m }, () => Array(n).fill(0))

    for (let i = 0; i < m; i++) {

        for (let j = 0; j < n; j++) {

            if (i == 0 && j == 0) {
                memo[i][j] = 1;
            } else {

                let up = 0
                let left = 0;
                if (i > 0) {
                    up = memo[i - 1][j];
                }

                if (j > 0) {
                    left = memo[i][j - 1];
                }
                memo[i][j] = left + up;
            }

        }
    }

    return memo[m - 1][n - 1]
};

Space Optimization

var uniquePaths = function (m, n) {
    // let memo = Array.from({ length: m }, () => Array(n).fill(0))
    let prev = []
    for (let i = 0; i < m; i++) {
        let curr = []
        for (let j = 0; j < n; j++) {
            if (i == 0 && j == 0) {
                curr[j] = 1;
            } else {

                let up = 0
                let left = 0;
                if (i > 0) {
                    up = prev[j];
                }

                if (j > 0) {
                    left = curr[j - 1];
                }
                curr[j] = left + up;
            }

        }

        prev = curr;

    }

    return prev[n - 1]
};

Tabulation

var uniquePathsWithObstacles = function (obstacleGrid) {


    let m = obstacleGrid.length;
    let n = obstacleGrid[0].length

    let dp = Array.from({ length: m }, () => Array(n).fill(0))

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (obstacleGrid[i][j] == 1) {
                dp[i][j] = 0;
                continue;
            }
            if (i == 0 && j == 0) {
                dp[0][0] = 1
                continue;
            }
            
            let up = 0

            let left = 0;

            if (i > 0) {
                up = dp[i - 1][j];
            }

            if (j > 0) {
                left = dp[i][j - 1];
            }
            dp[i][j] = left + up

        }
    }

    return dp[m - 1][n - 1]
};