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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Unique Paths and Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →