How do you approach Unique Paths?

The number of paths to any cell equals the sum of paths to the cell above and the cell to the left.

What is the time complexity of Unique Paths?

Time complexity: O(m * n). Space complexity: O(n) with space optimization.

What are common mistakes on Unique Paths?

Iterating the dimensions in an order that reads a cell before it has been written. Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input. Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.

← Back to problems

Unique Paths

MediumAlgorithms

Description

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.

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 3 ways: Right->Down->Down, Down->Right->Down, Down->Down->Right.

Constraints

- 1 <= m, n <= 100

Unique Paths: approach, complexity and pitfalls

A medium dynamic programming problem, graded against 6 test cases (3 of them hidden).

The pattern: Dynamic Programming

Overlapping subproblems solved once and reused - the pattern candidates fear most.

Reach for it when you see: "Number of ways", "minimum/maximum cost", or a recursion that recomputes the same state.

More Dynamic Programmingproblems →

If you are stuck

Show the 3-step hint ladder

The number of paths to any cell equals the sum of paths to the cell above and the cell to the left.
Use dynamic programming - build up from smaller subproblems.
You can optimize space to use only a single row.

The optimal approach

Show the approach: Dynamic Programming

Create a DP table where dp[i][j] = number of paths to reach cell (i, j). Each cell is the sum of the cell above and the cell to the left. Base case: first row and first column are all 1.

Time: O(m * n)
Space: O(n) with space optimization

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

Common Dynamic Programming mistakes

These apply to the pattern as a whole, not just this problem.

Iterating the dimensions in an order that reads a cell before it has been written.
Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input.
Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.