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 * 109.

Practice Link

Intuition#

To reach cell (m, n), the robot's last move was either from directly above (m-1, n) or directly to the left (m, n-1) — those are the only two cells that can move into (m, n). So the number of distinct paths to (m, n) is just the sum of the paths to those two predecessors:

ways(m, n) = ways(m-1, n) + ways(m, n-1)

with base case ways(0, 0) = 1 (already at the start — one trivial "path"), and any negative index contributes 0 (off the grid). This is the exact same "sum of two smaller subproblems" recurrence as Climbing Stairs, just over a 2D grid of states instead of a 1D line of steps — which is also why the top row and leftmost column of the tabulated dp grid are always 1: there's only one way to reach any cell along an edge (keep moving in the single direction that stays on the grid).

The five implementations below solve this same recurrence with increasing efficiency:

• Recursive: direct translation of the recurrence; recomputes the same (m, n) state repeatedly since many different paths pass through the same cell — exponential blowup.
• Memoized: caches uniquePathsUtil(m, n) the first time each state is computed, so every cell is solved once — O(m×n).
• Tabulation: fills a dp grid bottom-up (dp[i][j] = dp[i-1][j] + dp[i][j-1]), row by row, avoiding recursion overhead.
• Tabulation, space optimized: since dp[i][j] only ever needs the row above and the current row so far, the full grid collapses to two 1D rows (prevRow, currRow).
• Combinatorics: reframes the problem entirely — reaching the bottom-right always takes exactly (m-1) down-moves and (n-1) right-moves, in some order, out of (m-1)+(n-1) total moves. The count of distinct orderings is just the binomial coefficient C(m+n-2, m-1), computed iteratively to avoid overflow — no grid needed at all.

Implementation#

A. Recursive Approach#

class Solution {
public:
    int uniquePathsUtil(int m, int n)
    {
        if(m==0 && n==0)
            return 1;
        
        if(m<0 || n<0)
            return 0;

        return uniquePathsUtil(m-1,n) + uniquePathsUtil(m,n-1);
    }
    int uniquePaths(int m, int n) {
        return uniquePathsUtil(m-1,n-1);
    }
};

Time Limit Exceeded - Overlapping Cases

B. Memoization#

class Solution {
public:
    int uniquePathsUtil(int m, int n, vector<vector<int>> &memo)
    {
        if(m==0 && n==0)
            return 1;
        
        if(m<0 || n<0)
            return 0;

        if(memo[m][n] != -1)
            return memo[m][n];

        return memo[m][n] = uniquePathsUtil(m-1,n, memo) + uniquePathsUtil(m,n-1, memo);
    }
    int uniquePaths(int m, int n) {
        vector<vector<int>> memo(m, vector<int>(n,-1));
        return uniquePathsUtil(m-1,n-1, memo);
    }
};

Time Complexity - O(m * n)

Space Complexity - O((n-1)+(m-1)) + O(m * n)

B. Tabulation Solution#

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

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

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

Time Complexity - O(m * n)

Space Complexity - O(m * n)

Tabulation : Space Optimized#

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<int> prevRow(n, 1);
        vector<int> currRow(n, 0);
        currRow[0] = 1;

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

        return prevRow[n-1];
    }
};

Time Complexity - O(m * n)

Space Complexity - O(n)

Combinatronics#

class Solution {
public:
    int uniquePaths(int m, int n) {
        int s = (m-1) + (n-1);
        int r = (m-1);

        double ans = 1;

        for(int i=1;i<=r;i++)
        {
            ans = ans * (s-r+i)/i;
        }
        return (int)ans;
    }
};

Time Complexity - O(min(m,n))

Space Complexity - O(1)