Skip to main content

62. Unique Paths

medium

Count the number of distinct paths from the top-left to the bottom-right of an m x n grid moving only right or down. The cleanest grid-DP problem — also solvable in closed form with binomial coefficients.

By Sam K., Founder, InterviewChamp.AI · Last verified

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.

Constraints

  • 1 <= m, n <= 100

Examples

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Each cell's count = paths(above) + paths(left). Top row and left column are all 1 (only one way: straight right or straight down).

Hint 2

Bottom-up: fill an m x n grid with the recurrence.

Hint 3

Space optimization: only the previous row is needed — use a 1D array.

Solution approach

Reveal approach

Bottom-up DP. Allocate dp[m][n]. Initialize the first row and first column to 1 (only one way to reach any of those cells). For i = 1..m-1 and j = 1..n-1: dp[i][j] = dp[i-1][j] + dp[i][j-1]. Return dp[m-1][n-1]. Space-optimized version uses a 1D array of length n: dp[j] += dp[j-1] in place — the previous row's value is dp[j] before the update; the current row's value to the left is dp[j-1]. O(m * n) time, O(n) space. Closed form: C(m + n - 2, m - 1).

Complexity

Time
O(m * n)
Space
O(n)

Related patterns

  • dynamic-programming
  • grid-dp
  • combinatorics

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Bloomberg

More Dynamic Programming practice problems

See all Dynamic Programming problems →