Leetcode: Unique Paths

 This question is asked sometimes as Amazon, Mathworks, Google, and Uber. 

A robot is located at the top-left corner of a mxn grid (mark 'Start' in the diagram below). The robot is trying to reach the bottom right corner of the grid. How many possible unique paths are there? This is obviously a dynamic programming problem, which I will code in Javascript. Here are some examples: 

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 

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

Output: 6 

Constraints: 1 <= m, n <= 100 It's guaranteed that the answer will be less than or equal to 2 * 10^9.

First, when the robot is in the leftmost side, then the robot can go to the rightmost part. Now let's discuss the inner sells. One can move to cell (m, n - 1) or (m - 1, n) so we can add the unique paths of these. Now we can have an initial recursive solution, but it's not the most efficient exactly. 

var uniquePaths = function(m, n) {

     if(m == 1 || n == 1){

         return 1;

     }

     return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);

};

However, this solution isn't fast enough to pass all of the cases. 

The next approach we want to attempt is dynamic programming. 

The first way is to initialize a 2D array, and put the number of paths equal to 1 on the first row and the first column

Next, we want to iterate through the cells that d[col - 1][row] = d[col][row - 1] and return the last element in the list d[m - 1][n - 1].

So we initially fill everything with 1, and then attempt everything else. The code is here:

/**

 * @param {number} m

 * @param {number} n

 * @return {number}

 */

var uniquePaths = function(m, n) {

    //initialize an m x n array 

    let dp = new Array(m).fill(0).map(() => new Array(n));

    

    //have row 0 or column 0 equal to one path so far, since there is only one path going direct.

    //else have it equal to the addition of the previous 2 paths to the upper left.

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

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

           if(row == 0 || col == 0) {

               dp[row][col] = 1;

           } else {

               dp[row][col] = dp[row - 1][col] + dp[row][col - 1];

           }

        }

    }

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

};

The code is O(M x N), since we only need to go through the elements of the list.