62. Unique Paths - Solution & Explanation

The problem

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⁹.

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

Approach overview

Problem Overview: You are given an m x n grid. A robot starts at the top-left cell and can only move either right or down. The goal is to compute how many distinct paths lead to the bottom-right cell.

Approach 1: Dynamic Programming (O(m*n) time, O(m*n) space)

This problem fits classic dynamic programming. Each cell represents the number of ways to reach that position. If the robot can only move right or down, the paths to cell (i, j) must come from either (i-1, j) or (i, j-1). Build a 2D DP table where dp[i][j] = dp[i-1][j] + dp[i][j-1]. Initialize the first row and first column to 1 because there is only one way to move straight across or straight down. Iterate row by row to fill the table until reaching the bottom-right corner. This approach is intuitive, easy to implement in interviews, and clearly shows the transition relation between states.

Space can be optimized to O(n) by keeping only the current row because each state depends only on the left and the previous row value. This optimization is common in grid DP problems.

Approach 2: Combinatorial Approach (O(min(m,n)) time, O(1) space)

The robot must make exactly m-1 downward moves and n-1 right moves. That means every valid path is simply an arrangement of these moves. The total number of sequences is choosing positions for either the down or right moves. Mathematically this becomes the binomial coefficient:

C(m+n-2, m-1) or C(m+n-2, n-1).

This observation turns the grid problem into a math and combinatorics problem. Instead of building a DP table, compute the binomial coefficient iteratively using multiplication and division to avoid factorial overflow. Only iterate min(m-1, n-1) times while maintaining the result in a running product.

The combinatorial solution is significantly more memory efficient and faster for large grids since it avoids building the entire DP matrix. However, it requires recognizing the mathematical pattern behind the movement constraints.

Recommended for interviews: Start with the dynamic programming solution. It clearly demonstrates state transitions and grid reasoning, which interviewers expect when they see a matrix path-counting problem. After presenting DP, mention the combinatorial formula as an optimization. Showing both approaches proves you understand the problem structurally and mathematically.

Approach 1: Dynamic Programming Approach

The key idea in this approach is to use a 2D table to store the number of ways to reach each cell. Initialize the first row and first column by 1 because there is only one way to reach any cell in the first row (all rights) and the first column (all downs). For the rest of the cells, the number of ways to reach that cell is the sum of the number of ways to reach the cell directly above it and the cell directly to the left of it.

Python

def uniquePaths(m, n):
    dp = [[1] * n for _ in range(m)]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    return dp[m-1][n-1]

Java

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 j = 0; j < n; j++) {
            dp[0][j] = 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];
    }
}

C++

#include <vector>
using namespace std;

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];
}

JavaScript

var uniquePaths = function(m, n) {
    let dp = Array(m).fill().map(() => Array(n).fill(1));
    for(let i = 1; i < m; i++) {
        for(let j = 1; j < n; j++) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    return dp[m-1][n-1];
};

int uniquePaths(int m, int n) {
    int dp[m][n];
    for (int i = 0; i < m; i++) {
        dp[i][0] = 1;
    }
    for (int j = 0; j < n; j++) {
        dp[0][j] = 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];
}

public 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 j = 0; j < n; j++)
            dp[0,j] = 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];
    }
}

Python uses list comprehension to initialize the 2D list dp. Looping over the list fills in the number of unique paths for all cells, with the solution found at dp[m-1][n-1].

Complexity

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

Try this approach in the editor

Approach 2: Combinatorial Approach

A different method is to use combinatorics. The robot makes a total of (m + n - 2) moves, consisting of (m - 1) downward moves and (n - 1) rightward moves. The number of unique paths to organize these actions is the number of combinations of downs and rights: Combination(m+n-2, m-1) or Combination(m+n-2, n-1). This approach avoids the need for additional memory allocation for simple calculations.

Python

import math

def uniquePaths(m, n):
    return math.comb(m + n - 2, m - 1)

Java

class Solution {
    private long combination(int n, int k) {
        k = Math.min(k, n - k);
        long result = 1;
        for (int i = 1; i <= k; i++, n--) {
            result = result * n / i;
        }
        return result;
    }

    public int uniquePaths(int m, int n) {
        return (int) combination(m + n - 2, m - 1);
    }
}

C++

#include <algorithm>

long long combination(int n, int k) {
    k = std::min(k, n - k);
    long long result = 1;
    for(int i = 1; i <= k; i++, n--) {
        result = result * n / i;
    }
    return result;
}

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

JavaScript

var uniquePaths = function(m, n) {
    const combination = (n, k) => {
        k = Math.min(k, n - k);
        let result = 1;
        for (let i = 1; i <= k; i++, n--) {
            result = result * n / i;
        }
        return result;
    };
    return combination(m + n - 2, m - 1);
};

#include <stdio.h>

long long combination(int n, int r) {
    if(r > n / 2) r = n - r;
    long long ans = 1;
    for(int i = 1; i <= r; i++, n--) {
        ans = ans * n / i;
    }
    return ans;
}

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

public class Solution {
    private long Combination(int n, int k) {
        k = Math.Min(k, n - k);
        long result = 1;
        for (int i = 1; i <= k; i++, n--) {
            result = result * n / i;
        }
        return result;
    }

    public int UniquePaths(int m, int n) {
        return (int) Combination(m + n - 2, m - 1);
    }
}

Pythons's math library directly provides the comb function for comfortable calculation through native functionality.

Complexity

Time Complexity: O(1) due to efficient libraries, Space Complexity: O(1).

Try this approach in the editor

Approach 3: Dynamic Programming

We define f[i][j] to represent the number of paths from the top left corner to (i, j), initially f[0][0] = 1, and the answer is f[m - 1][n - 1].

Consider f[i][j]:

If i > 0, then f[i][j] can be reached by taking one step from f[i - 1][j], so f[i][j] = f[i][j] + f[i - 1][j];
If j > 0, then f[i][j] can be reached by taking one step from f[i][j - 1], so f[i][j] = f[i][j] + f[i][j - 1].

Therefore, we have the following state transition equation:

$f[i][j] = \begin{cases} 1 & i = 0, j = 0 \ f[i - 1][j] + f[i][j - 1] & otherwise \end{cases}

The final answer is f[m - 1][n - 1].

The time complexity is O(m times n), and the space complexity is O(m times n). Here, m and n are the number of rows and columns of the grid, respectively.

We notice that f[i][j] is only related to f[i - 1][j] and f[i][j - 1], so we can optimize the first dimension space and only keep the second dimension space, resulting in a time complexity of O(m times n) and a space complexity of O(n)$.

TypeScript

function uniquePaths(m: number, n: number): number {
    const f: number[][] = Array(m)
        .fill(0)
        .map(() => Array(n).fill(0));
    f[0][0] = 1;
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            if (i > 0) {
                f[i][j] += f[i - 1][j];
            }
            if (j > 0) {
                f[i][j] += f[i][j - 1];
            }
        }
    }
    return f[m - 1][n - 1];
}

func uniquePaths(m int, n int) int {
	f := make([][]int, m)
	for i := range f {
		f[i] = make([]int, n)
	}
	f[0][0] = 1
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if i > 0 {
				f[i][j] += f[i-1][j]
			}
			if j > 0 {
				f[i][j] += f[i][j-1]
			}
		}
	}
	return f[m-1][n-1]
}

Rust

impl Solution {
    pub fn unique_paths(m: i32, n: i32) -> i32 {
        let (m, n) = (m as usize, n as usize);
        let mut f = vec![1; n];
        for i in 1..m {
            for j in 1..n {
                f[j] += f[j - 1];
            }
        }
        f[n - 1]
    }
}

Try this approach in the editor

Approach 4: Default Approach

TypeScript

function uniquePaths(m: number, n: number): number {
    const f: number[][] = Array(m)
        .fill(0)
        .map(() => Array(n).fill(1));
    for (let i = 1; i < m; ++i) {
        for (let j = 1; j < n; ++j) {
            f[i][j] = f[i - 1][j] + f[i][j - 1];
        }
    }
    return f[m - 1][n - 1];
}

func uniquePaths(m int, n int) int {
	f := make([][]int, m)
	for i := range f {
		f[i] = make([]int, n)
		for j := range f[i] {
			f[i][j] = 1
		}
	}
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			f[i][j] = f[i-1][j] + f[i][j-1]
		}
	}
	return f[m-1][n-1]
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Dynamic Programming Approach	Time Complexity: O(m * n), Space Complexity: O(m * n).
Combinatorial Approach	Time Complexity: O(1) due to efficient libraries, Space Complexity: O(1).
Dynamic Programming	–
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
Dynamic Programming (2D Grid)	O(m*n)	O(m*n)	Best for explaining the grid transition logic in interviews
Dynamic Programming (Space Optimized)	O(m*n)	O(n)	When memory usage matters but DP reasoning is still desired
Combinatorial Formula	O(min(m,n))	O(1)	Optimal when recognizing the binomial pattern in grid paths

Frequently asked questions

Is Unique Paths easy or hard?

Unique Paths is generally considered a medium-level problem. The DP solution is straightforward once the recurrence relation is identified, but recognizing the combinatorial shortcut requires stronger mathematical insight.

What is the best approach for Unique Paths?

Dynamic Programming is the most common approach because it models the grid directly with the transition dp[i][j] = dp[i-1][j] + dp[i][j-1]. It runs in O(m*n) time and clearly shows how each path builds from previous cells. A combinatorial solution using binomial coefficients is more optimal in space and runs in O(min(m,n)) time.

What data structure is used in Unique Paths?

The dynamic programming solution typically uses a 2D array (or a 1D optimized array) to store the number of paths to each grid cell. The combinatorial solution instead relies on mathematical computation without additional data structures.

What is the time complexity of Unique Paths?

The standard dynamic programming solution runs in O(m*n) time because every cell in the grid is computed once. The combinatorial math approach improves this to O(min(m,n)) by calculating the binomial coefficient C(m+n-2, m-1) iteratively.

Unique Paths Python or Java solution approach?

Both Python and Java implementations usually follow the DP grid approach where a matrix is filled using dp[i][j] = dp[i-1][j] + dp[i][j-1]. Many optimized solutions use a single 1D array to reduce space from O(m*n) to O(n).

How to solve Unique Paths in O(n) or better time?

Recognize that the robot must take exactly m-1 down moves and n-1 right moves. The number of valid sequences equals C(m+n-2, m-1). Computing this binomial coefficient iteratively takes O(min(m,n)) time and O(1) space without building the grid.

Is Unique Paths asked at Google, Amazon, or Meta?

Unique Paths is a common grid dynamic programming question asked across major tech companies including Amazon, Google, and Meta. It tests understanding of DP state transitions and recognizing combinatorial patterns.

Unique Paths solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming Approach

Approach 2: Combinatorial Approach

Approach 3: Dynamic Programming

Approach 4: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Unique Paths solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming Approach

Approach 2: Combinatorial Approach

Approach 3: Dynamic Programming

Approach 4: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems