Unique Paths

Unique Paths: 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 * 10^9.

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

Try this Problem on your own or check similar problems:

Solution:

Java
JavaScript
Python
C++

class Solution {
  public int uniquePaths(int m, int n) {
      int[] dp = new int[n];
      Arrays.fill(dp, 1);

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

      return dp[n-1];
  }
}

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function (m, n) {
  let dp = new Array(n).fill(1);

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

  return dp[n - 1];
};

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [1] * n

        for i in range(1, m):
            for j in range(1, n):
                dp[j] += dp[j - 1]

        return dp[n - 1]

class Solution {
public:
    int uniquePaths(int m, int n) {
        std::vector<int> dp(n, 1);

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

        return dp[n - 1];
    }
};

Time/Space Complexity:

Time Complexity: O(m*n)
Space Complexity: O(n)

Explanation:

A recursive solution would be to start from the first row and first column square and converge to m row and n column. There are two base cases:

we're either out of boundary or we return 0
or we're at m and n and we return 1

Java
JavaScript
Python
C++

class Solution {
    public int uniquePaths(int m, int n) {
        return helper(1, 1, m, n);
    }
    private int helper(int x, int y, int m, int n){
        if(x > m || y > n) return 0;
        if(x == m && y == n) return 1;

        return helper(x+1, y, m, n) + helper(x, y + 1, m, n);
    }
}

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function (m, n) {
  return helper(1, 1, m, n);
};

function helper(x, y, m, n) {
  if (x > m || y > n) return 0;
  if (x === m && y === n) return 1;

  return helper(x + 1, y, m, n) + helper(x, y + 1, m, n);
}

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
         return self.helper(1, 1, m, n)

    def helper(self, x, y, m, n):
        if x > m or y > n:
            return 0
        if x == m and y == n:
            return 1

        return self.helper(x + 1, y, m, n) + self.helper(x, y + 1, m, n)

class Solution {
public:
    int uniquePaths(int m, int n) {
        return helper(1, 1, m, n);
    }

private:
    int helper(int x, int y, int m, int n) {
        if (x > m || y > n) return 0;
        if (x == m && y == n) return 1;

        return helper(x + 1, y, m, n) + helper(x, y + 1, m, n);
    }
};

Of course this will not perform well, and we could use memoization (matrix mXn to store current ways to get to some position dp[i][j], i represents the position of the row and j position of the column), but let's move to the bottom up tabulation approach:

Java
JavaScript
Python
C++

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for(int i = 0; i < m; ++i){
            dp[i][0] = 1;
        }
        for(int i = 0; i < n; ++i){
            dp[0][i] = 1;
        }
        for(int i = 1; i < m; ++i){
            for(int j = 1; j < n; ++j){
                dp[i][j] = dp[i][j-1] + dp[i-1][j];
            }
        }

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

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function (m, n) {
  const dp = new Array(m).fill(0).map(() => new Array(n).fill(0));

  for (let i = 0; i < m; i++) {
    dp[i][0] = 1;
  }

  for (let i = 0; i < n; i++) {
    dp[0][i] = 1;
  }

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

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

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[0] * n for _ in range(m)]

        for i in range(m):
            dp[i][0] = 1

        for i in range(n):
            dp[0][i] = 1

        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i][j-1] + dp[i-1][j]

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

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n, 0));

        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }

        for (int i = 0; i < n; i++) {
            dp[0][i] = 1;
        }

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

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

We know that there is only way to get to only position located in the first row or first column (since we can only move down and right), for all other positions we can either get there from the left or from the top dp[i][j] = dp[i][j-1] + dp[i-1][j]; where dp[i][j-1] is the left square from our current position, and dp[i-1][j] is the square above it. Finally, we return the value of the last position in the matrix m row, n column. But do we need a matrix to keep track of all positions, or can we just use an array to keep track of the last calculation? It turns out an array would be enough for us to perform the calculations. Each time we just add the total number of ways to get to our left position dp[j-1] to the current calculation on how we can get to our current position using the square above (previous calculation dp[j]). Final solution is given in the Solution section.

Example 1:​

Example 2:​

Constraints:​

Solution:​

Time/Space Complexity:​