51. Unique Paths
mediumAsked at VercelCount 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 Sam K., Founder, InterviewChamp.AI · Last verified
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
m = 3, n = 728Example 2
m = 3, n = 23Approaches
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.
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.