x 62. Unique Paths

Unique Paths - LeetCodeLeetCode

Recursive

 const memo = {};
 
 const uniquePaths = function(m, n) {
     const key = m + ',' + n;
     if (key in memo) return memo[key];
     if (m === 1 || n === 1) return 1
     if (m === 0 || n === 0) return 0;
     
     memo[key] = uniquePaths(m-1, n) + uniquePaths(m, n-1);
     return memo[key];
};

2nd try

time: O(m x n)

space: O(m or n)

// this reduces time
// const memo = {};
const memo = {};
var uniquePaths = function (m, n) {

    if (memo['' + m + n] !== undefined) {
        return memo['' + m + n];
    }

    const arr = new Array(m).fill(1);
    for (let i = 1; i < n; i++) {
        for (let j = 1; j < m; j++) {
            arr[j] += arr[j - 1];
        }
    }

    memo['' + m + n] = arr[m - 1];
    return arr[m - 1];
};

1st try

time: O(m x n)

space: O(m x n)

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
    const matrix = new Array(m);

    matrix[0] = new Array(n).fill(1);
    for (let i = 1; i < m; i++) {
        matrix[i] = new Array(n);
        matrix[i][0] = 1;
    }

    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            matrix[i][j] = matrix[i - 1][j] + matrix[i][j - 1];
        }
    }

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