LeetCode 62. Unique Paths (javascript solution)

#algorithms #javascript

Description:

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

Solution:

Time Complexity : O(n^2)
Space Complexity: O(n)

var uniquePaths = function(m, n) {
    // Create dp array
    const dp = new Array(n + 1).fill(1);

    // Populate dp array
    for(let row = m - 1; row > 0; row--){
        for(let col = n - 1; col > 0; col--){
            dp[col] = dp[col] + dp[col + 1];
        }
    }
    return dp[1];
}