What is the Unique Paths Problem?
Learn the unique paths grid DP problem, its recurrence, complexity, and combinatorial shortcut for coding interviews.
Expected Interview Answer
The unique paths problem counts how many distinct routes exist from the top-left to the bottom-right of an m x n grid when only right or down moves are allowed, solved in O(m * n) time by summing the number of ways to reach each cell from its top and left neighbors.
Define dp[i][j] as the number of distinct paths to reach cell (i, j). Since the only moves are right and down, a cell can be reached either from directly above or directly to the left, giving the recurrence dp[i][j] = dp[i-1][j] + dp[i][j-1]. Every cell in the first row and first column has exactly one path (a straight line), so they are all initialized to 1. The final answer is dp[m-1][n-1]. This is the grid analogue of Pascal’s triangle, and it also has a closed-form combinatorial solution, C(m+n-2, m-1), since any path is exactly (m-1) down-moves interleaved with (n-1) right-moves.
- O(m * n) DP time, or O(min(m,n)) with the combinatorial formula
- O(n) space with a rolling 1D array
- Directly generalizes to counting paths with obstacles
- Reinforces combinatorics-DP equivalence for interviews
AI Mentor Explanation
A groundskeeper wants to know how many distinct routes a mower can take from one corner of the field to the diagonally opposite corner, moving only toward the boundary rope or toward the far end, never backward. The number of ways to reach any patch of grass equals the number of ways to reach the patch above it plus the number of ways to reach the patch to its left, since those are the only two doors in. Every patch along the very first row or first column has exactly one route in, a straight line along the edge. Summing this up patch by patch tells the groundskeeper exactly how many distinct mowing routes exist without ever tracing a single one by hand.
Step-by-Step Explanation
Step 1
Define the state
dp[i][j] is the number of distinct paths from (0,0) to (i,j) moving only right or down.
Step 2
Initialize the edges
Every cell in the first row and first column equals 1, since there is exactly one straight-line route to reach it.
Step 3
Apply the recurrence
dp[i][j] = dp[i-1][j] + dp[i][j-1] for every other cell, summing routes from above and from the left.
Step 4
Read the answer or use combinatorics
dp[m-1][n-1] is the answer, equivalent to the binomial coefficient C(m+n-2, m-1).
What Interviewer Expects
- State the recurrence and explain why it sums two neighbors, not takes a minimum
- Correctly initialize the first row and column to 1
- Give O(m * n) time and mention the O(n) space-optimized version
- Recognize the closed-form combinatorial equivalence when asked
Common Mistakes
- Confusing this with minimum path sum and taking a min instead of a sum
- Initializing edge cells to 0 instead of 1
- Overflow-prone factorial computation when using the combinatorial formula on large grids
- Forgetting the obstacle variant requires zeroing out blocked cells entirely
Best Answer (HR Friendly)
“Unique paths asks how many distinct ways there are to get from one corner of a grid to the other, moving only right or down. I solve it by counting, for each cell, how many ways there are to reach it from the cell above plus the cell to the left, building the count up from the top-left corner.”
Code Example
def unique_paths(m, n):
dp = [1] * n
for i in range(1, m):
for j in range(1, n):
dp[j] += dp[j - 1]
return dp[n - 1]
def unique_paths_combinatorial(m, n):
from math import comb
return comb(m + n - 2, m - 1)Follow-up Questions
- How would you solve unique paths when some grid cells are obstacles?
- Why is the answer equivalent to a binomial coefficient?
- How would you count paths if diagonal moves were also allowed?
- How would you list all the actual paths instead of just counting them?
MCQ Practice
1. What is the recurrence relation for the unique paths DP?
A cell can only be reached from above or from the left, so the count of paths into it is the sum of both.
2. What value should every cell in the first row and first column be initialized to?
Edge cells have exactly one straight-line path reaching them, so they are initialized to 1.
3. What is the closed-form combinatorial answer for unique paths on an m x n grid?
Any path is exactly (m-1) down moves and (n-1) right moves in some order, giving the binomial coefficient C(m+n-2, m-1).
Flash Cards
What is the recurrence for unique paths? — dp[i][j] = dp[i-1][j] + dp[i][j-1].
What value initializes the first row and column? — 1, since there is only one straight-line path to reach each edge cell.
What is the time complexity of the DP solution? — O(m * n), visiting every cell once.
What closed-form formula also solves unique paths? — The binomial coefficient C(m+n-2, m-1).