53. Unique Paths
mediumAsked at RedditCount the number of paths from top-left to bottom-right of an m x n grid (right/down only). Reddit uses this DP problem as a clean grid-DP warm-up before harder routing problems.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Reddit loops.
- Glassdoor (2026-Q1)— Reddit phone screen, DP warm-up.
Problem
There is a robot on an m x n grid. The robot is initially located at the top-left corner. 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 that the robot can take to reach the bottom-right corner.
Constraints
1 <= m, n <= 100
Examples
Example 1
m = 3, n = 728Example 2
m = 3, n = 23Approaches
1. Recursive (no memo)
paths(i, j) = paths(i-1, j) + paths(i, j-1).
- Time
- O(2^(m+n))
- Space
- O(m+n)
function uniquePaths(m, n) {
function dfs(i, j) {
if (i === 0 && j === 0) return 1;
if (i < 0 || j < 0) return 0;
return dfs(i - 1, j) + dfs(i, j - 1);
}
return dfs(m - 1, n - 1);
}Tradeoff: Exponential. TLE for medium m, n.
2. DP rolling 1D (optimal)
dp[j] = number of paths to (i, j). For each row, 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) memory by rolling rows. Math closed-form is C(m+n-2, m-1) but DP is interview-canonical.
Reddit-specific tips
Reddit interviewers expect the DP version with rolling memory. Bonus signal: mention the closed-form binomial C(m+n-2, m-1) and explain when you'd use one vs. the other.
Common mistakes
- Allocating m*n 2D matrix when 1D rolling works.
- Off-by-one on row/column initialization (fill with 1).
- Not handling the m=1 or n=1 base case (answer is 1).
Follow-up questions
An interviewer at Reddit may pivot to one of these next:
- Unique Paths II (LC 63) — with obstacles.
- Minimum path sum (LC 64).
- Dungeon game (LC 174).
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why does the closed-form work?
Every path has exactly m-1 downs and n-1 rights, in some order. Choose positions for the downs: C(m+n-2, m-1).
When would the 2D DP be needed?
When you need the path itself, or when transitions depend on the row direction.