Skip to main content
Talentd

Unique Paths - Solution & Explanation

MediumMathDynamic ProgrammingCombinatorics23 min readAsked at: Amazon, Microsoft, Goldman Sachs +18
Practice this problem

Problem Statement

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.

 

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.

This C implementation uses a 2D array dp to keep track of the number of ways to reach each cell. After initializing the first row and column to 1, we iteratively compute the number of ways for other cells. The final result is stored in dp[m-1][n-1], which represents the bottom-right corner.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m * n) because each cell is computed once. Space Complexity: O(m * n) for the 2D DP array.

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.

This C code calculates the combinatorial value of picking (m-1) from (m+n-2) using an iterative approach to avoid overflow issues compared to factorial division directly.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(min(m, n)) for optimal comb calculations. 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)$.

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Approach 4: Default Approach

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming Approach

Time Complexity: O(m * n) because each cell is computed once. Space Complexity: O(m * n) for the 2D DP array.

Combinatorial Approach

Time Complexity: O(min(m, n)) for optimal comb calculations. Space Complexity: O(1).

Dynamic Programming—
Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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 FormulaO(min(m,n))O(1)Optimal when recognizing the binomial pattern in grid paths

Video Solution

Unique Paths - Dynamic Programming - Leetcode 62 • NeetCode • 203,107 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Unique Paths with our built-in code editor and test cases.

Practice on FleetCode
Previous

Dungeon Game

Next

Minimum Cost Homecoming of a Robot in a Grid