Skip to content

Link to Question

MEDIUM

Unique Paths

There is a robot located at the top-left corner of an 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').

How many possible unique paths are there?

Example

Input: 

m = 3, n = 7
Output: 
28

Explanation: There are 28 unique paths from the top-left to the bottom-right corner.

Constraints

  • 1 ≤ m, n ≤ 100

Solution: Dynamic Programming

  • Time Complexity: O(mn)
  • Space Complexity: O(n)
C++
class Solution {
public:
    int uniquePaths(int m, int n) {
        int arr[101][101] = {0};
        arr[0][0] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {           
                if (i - 1 >= 0) arr[i][j] += arr[i-1][j];
                if (j - 1 >= 0) arr[i][j] += arr[i][j-1];
            }
        }

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