51. Unique Paths

Q: Why does rolling-row work?

When computing dp[i][j], we only need dp[i-1][j] (= old dp[j] before update) and dp[i][j-1] (= already-updated dp[j-1]). The 1D array holds the previous row, and we update left-to-right.

Q: Combinatorial vs DP — which to pick?

Combinatorial is faster and cleaner but easy to overflow in some languages. DP is the safer 'I understand the recurrence' signal for interviews.

mediumAsked at Vercel

Count the number of unique paths from top-left to bottom-right in an m x n grid, moving only right or down. Vercel asks this as the simplest 2D DP — same shape as counting valid deploy paths from source commit to target environment.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-20

Source citations

Public interview reports confirming this problem appears in Vercel loops.

Glassdoor (2025-Q4)— Vercel screen DP warm-up.
LeetCode Discuss (2026-Q1)— Listed in Vercel interview pool.

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

Constraints

1 <= m, n <= 100

Examples

Example 1

Input

m = 3, n = 7

Output

Example 2

Input

m = 3, n = 2

Output

Approaches

1. Combinatorial formula

Total moves = (m-1) + (n-1); choose which (m-1) are down. Answer = C(m+n-2, m-1).

Time: O(min(m,n))
Space: O(1)

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

Tradeoff: Fastest if you know combinatorics. Vercel accepts it but the DP version is what they grade.

2. Bottom-up DP with rolling row (optimal interview answer)

dp[i][j] = dp[i-1][j] + dp[i][j-1], with dp[0][*] = dp[*][0] = 1. Roll to 1D: dp[j] += dp[j-1].

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

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

Tradeoff: O(n) extra space using the rolling-row trick. The recurrence becomes a single in-place update: dp[j] += dp[j-1].

Vercel-specific tips

Vercel grades the rolling-row DP. Bonus signal: writing the 2D DP first to motivate the recurrence, then collapsing to 1D by reusing dp[j] as both 'old row's column' and 'new row's column' at the right moment.

Common mistakes

Initializing only dp[0][0] = 1 — first row and column must also be 1.
Iterating in the wrong order on the rolling-row — reading dp[j-1] before updating dp[j] preserves the previous row's value.
Floating-point in the combinatorial version — must Math.round at the end.

Follow-up questions

An interviewer at Vercel may pivot to one of these next:

Unique Paths II (LC 63) — with obstacles.
Minimum Path Sum (LC 64) — weighted grid.
Number of paths in a DAG with k edges.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why does rolling-row work?

When computing dp[i][j], we only need dp[i-1][j] (= old dp[j] before update) and dp[i][j-1] (= already-updated dp[j-1]). The 1D array holds the previous row, and we update left-to-right.

Combinatorial vs DP — which to pick?

Combinatorial is faster and cleaner but easy to overflow in some languages. DP is the safer 'I understand the recurrence' signal for interviews.

Practice these live with InterviewChamp.AI

Drill Unique Paths and other Vercel interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →