Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Count how many ways a robot reaches the bottom-right of an m×n grid moving only right or down. Every cell's path count is the sum of the cell above and the cell to its left: dp[i][j] = dp[i-1][j] + dp[i][j-1]. That's O(m·n); roll the table to one row for O(n) space, or skip DP entirely with the closed-form C(m+n-2, m-1).
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you can derive a 2D DP recurrence from scratch — identify the state, the transition, and the base cases — and then optimise space by noticing the dependency only reaches one row back.
Where candidates slip
Forgetting to initialise the first row/column to 1 (so everything stays 0), or mutating the rolled 1D array in the wrong order so a cell reads a value that was already overwritten this pass.
How to stand out
Name the closed form C(m+n-2, m-1) and explain why path-counting on a monotone grid is just 'choose where the downs go among all the moves'. Then mention the O(n) rolled-array optimisation unprompted.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewCount paths on an m×n right/down gridComfortable with combinatorics?YesNo / asked for DPExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 3
2D DP Table — Fill the Grid
1Hint 1Explore hintHide hint
How many ways can you reach a specific cell? You could only have stepped in from the cell directly above it or directly to its left.
2Hint 2Explore hintHide hint
So the count for a cell is the sum of the counts of those two neighbours. What are the counts along the very first row and column?
3Hint 3Explore hintHide hint
Initialise the first row and first column to 1 (one straight-line path each), then fill the rest with dp[i][j] = dp[i-1][j] + dp[i][j-1].
A · Core idea
Define dp[i][j] as the number of unique paths from the start to cell (i, j). Fill the grid row by row; the answer is the bottom-right cell dp[m-1][n-1].
Why the recurrence is `up + left`. Because the robot only moves right or down, the last step into any cell (i, j) was either a down (arriving from (i-1, j)) or a right (arriving from (i, j-1)). Those two predecessors cover every way to land on the cell and they never overlap, so the number of paths to (i, j) is exactly the sum of the paths to those two cells. That's the whole algorithm — dp[i][j] = dp[i-1][j] + dp[i][j-1].
Why the first row and column are all 1. A cell in the top row can only be reached by moving right the whole way — there's no row above to drop in from. Likewise the leftmost column is reachable only by moving straight down. Each of those has exactly one path, so they're our base cases. Forget to set them and every cell stays 0, the single most common bug in this problem.
Why this is the natural first answer. It mirrors how you'd reason on a whiteboard: 'how do I get here? From above or from the left.' It's O(m·n) time, which is optimal for filling a grid, and it's trivially correct. We only improve the space afterward — the time is already as good as a tabular DP gets.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
m = 3, n = 3Array state
row 2 start
Leftmost cell is base case = 1
6C · Code with teaching comments
Reference implementation previewpublic int uniquePaths(int m, int n) { int[][] dp = new int[m][n]; for (int i = 0; i < m; i++) dp[i][0] = 1; for (int j = 0; j < n; j++) dp[0][j] = 1; for (int i = 1; i < m; i++) {Explore the full codeHide the full code
D · Why it works and complexityO(m·n) timeO(m·n) spaceOpen the invariant and proofExplore the proofHide the proof
The mental unlock is reading the recurrence backwards: don't ask 'where can I go from here', ask 'where could I have come from to land here'. On a right/down grid the answer is always 'up or left', and summing those two predecessor counts is the entire transition. Master that reversal and most grid DPs fall out the same way.
ComplexityO(m·n) time, O(m·n) space — We touch each of the m·n cells exactly once and do O(1) addition per cell, so time is O(m·n). We store the whole table, so space is O(m·n).
E · Edge cases and pitfalls5m = 1, n = 1 — Both loops over inner cells never execute; dp[0][0] stays 1 from the base-case fill → returns 1.Explore edge casesHide edge cases
Edge cases handled
m = 1, n = 1Both loops over inner cells never execute; dp[0][0] stays 1 from the base-case fill → returns 1.m = 1, n = 5Only the top row exists, all 1s; returns dp[0][4] = 1 — the single straight-right path.
Pitfalls
- Leaving the first row/column at 0 — every inner cell then sums to 0 and you return 0.
- Allocating dp as new int[n][m] (axes swapped) and indexing m,n inconsistently.
- Returning dp[m][n] instead of dp[m-1][n-1] — off-by-one out of bounds.
Approach 2 of 3
Rolled 1D DP — One Row of Memory
1Hint 1Explore hintHide hint
Look at the 2D recurrence: dp[i][j] depends only on row i-1 and the cell to its left in row i. Do you really need every past row?
2Hint 2Explore hintHide hint
Keep just one array of length n representing the current row as you sweep down. Before you overwrite a cell, what does its old value represent?
3Hint 3Explore hintHide hint
Process left-to-right: row[j] += row[j-1]. The old row[j] is still the 'above' value, and row[j-1] was just updated to the 'left' value.
A · Core idea
Collapse the table to a single array row of length n, initialised to all 1s (that's the first row). For each subsequent row, sweep left to right doing row[j] += row[j-1].
Why one array is enough. In the 2D recurrence dp[i][j] = dp[i-1][j] + dp[i][j-1], the only previous row referenced is i-1. Once we've finished computing row i, row i-1 is never read again. So instead of m rows we keep one and overwrite it in place, reusing the same memory for every row.
Why the left-to-right order is exactly right. When we reach row[j], its current (not-yet-updated) value is still the value from the row above — that's our dp[i-1][j]. And row[j-1] was updated a moment ago in this same pass — that's dp[i][j-1], the cell to the left. So row[j] = row[j] + row[j-1] reads one stale value (above) and one fresh value (left), which is precisely the recurrence. Sweep the other direction and you'd clobber the 'above' value before using it.
Why this matters in an interview. Rolling a 2D DP to 1D is the single most-asked DP follow-up: 'can you do it in less space?' Showing it unprompted signals you understand the dependency structure of your own recurrence, not just that it produces the right number.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
m = 3, n = 3Array state
top row
Initial layer, all ones
6C · Code with teaching comments
Reference implementation previewpublic int uniquePaths(int m, int n) { int[] row = new int[n]; Arrays.fill(row, 1); for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) {Explore the full codeHide the full code
D · Why it works and complexityO(m·n) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
The trick is recognising that row[j] does double duty across a single update: just before the +=, it's the cell from the previous row; just after, it's the cell in the current row. That overlap is only safe because the recurrence reaches back exactly one row and one column — a property worth stating out loud, because it's what licenses the optimisation.
ComplexityO(m·n) time, O(n) space — Same m·n cell updates as the 2D version, so time stays O(m·n). We keep only one row of length n, so space drops to O(n).
E · Edge cases and pitfalls5m = 1, n = 4 — Outer loop (i from 1) never runs; row stays [1,1,1,1] → returns 1.Explore edge casesHide edge cases
Edge cases handled
m = 1, n = 4Outer loop (i from 1) never runs; row stays [1,1,1,1] → returns 1.m = 4, n = 1row has length 1 = [1]; inner loop never runs; returns row[0] = 1.
Pitfalls
- Sweeping j from high to low — overwrites row[j-1] before it's used, breaking the recurrence.
- Allocating row of length m instead of n when m ≠ n.
- Re-initialising row inside the outer loop — wipes out the accumulated counts.
Approach 3 of 3 · Optimal
Combinatorics — Closed Form C(m+n-2, m-1) (Optimal)
1Hint 1Explore hintHide hint
Strip the grid away. Every path is a sequence of moves — how many downs and how many rights does each path contain, regardless of order?
2Hint 2Explore hintHide hint
You always make exactly m-1 downs and n-1 rights, for m+n-2 total moves. A path is just a choice of which positions are the downs.
3Hint 3Explore hintHide hint
So the count is the binomial coefficient C(m+n-2, m-1). Compute it multiplicatively to avoid overflowing a factorial.
A · Core idea
Forget the grid for a second and look at a path as a string of moves. Every valid path is a sequence of exactly m-1 Downs and n-1 Rights — m+n-2 moves total — and any ordering of those moves is a distinct valid path.
Why it's a 'choose' problem. Counting orderings of m+n-2 moves where m-1 are identical Downs and the rest identical Rights is exactly the definition of a binomial coefficient: pick which m-1 of the m+n-2 slots hold the Downs and the Rights fill the rest. That's C(m+n-2, m-1). No grid, no table — the answer is a single number from Pascal's triangle.
Why compute it multiplicatively. C(m+n-2, m-1) written as (m+n-2)! / ((m-1)!·(n-1)!) is correct math but dangerous code: the factorials explode far past the (small) final answer and overflow. Instead build the result incrementally as result *= (n - 1 + i) / i for i = 1..m-1. Each partial product is itself a valid binomial coefficient, so the intermediate values stay bounded and the division is always exact.
Why iterate over the smaller dimension. C(a, k) = C(a, a-k), so choosing min(m-1, n-1) as the loop length minimises both the iteration count and the size of the running product. It's a small touch, but it's the difference between an answer that's merely correct and one that's deliberate.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
m = 3, n = 7Interactive diagram
Picking the right approach
setupAll three approaches are correct; the decision is how much space and cleverness you want to spend.
28C · Code with teaching comments
D · Why it works and complexityO(min(m, n)) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
The leap from 'fill a grid' to 'choose where the downs go' is the real lesson: a DP that has no obstacles and a perfectly regular transition is often a combinatorial identity in disguise. Spotting that collapses O(m·n) work into O(min(m,n)) and zero auxiliary memory — and it's the kind of reframing that makes an interviewer lean in.
ComplexityO(min(m, n)) time, O(1) space — We multiply and divide through min(m-1, n-1) terms to build the binomial, each step O(1), so time is O(min(m, n)). Only a couple of accumulator variables → O(1) space.
E · Edge cases and pitfalls5m = 1, n = 1 — k = min(0,0) = 0; the loop never runs; result stays 1 → correct single path.Explore edge casesHide edge cases
Edge cases handled
m = 1, n = 1k = min(0,0) = 0; the loop never runs; result stays 1 → correct single path.m = 3, n = 2k = min(2,1) = 1, big = 2; i=1 → result = 1*3/1 = 3 = C(3,1) → 3 paths.
Pitfalls
- Computing (m+n-2)! / ((m-1)!(n-1)!) directly — the factorials overflow long before the answer would.
- Doing `result *= (big + i); result /= i;` as two statements where the multiply alone overflows int — keep it one expression and/or use long.
- Looping over the larger dimension — still correct but more iterations and bigger intermediate products than necessary.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int uniquePaths(int m, int n) { int k = Math.min(m - 1, n - 1); int big = (m - 1) + (n - 1) - k; // the larger of m-1, n-1 long result = 1; for (int i = 1; i <= k; i++) {Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Uninitialised base row/column
If the first row and column aren't set to 1, every inner cell sums two zeros and the function returns 0 for every grid.
Explore the code comparisonHide the code comparison
Uninitialised base row/column
If the first row and column aren't set to 1, every inner cell sums two zeros and the function returns 0 for every grid.
Don't write this
int[][] dp = new int[m][n]; // all zeros
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++)
dp[i][j] = dp[i-1][j] + dp[i][j-1];
return dp[m-1][n-1]; // always 0Write this instead
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int j = 0; j < n; j++) dp[0][j] = 1;
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++)
dp[i][j] = dp[i-1][j] + dp[i][j-1];
return dp[m-1][n-1];2Wrong sweep direction in the rolled array
Going right-to-left overwrites row[j-1] (the 'left') before the cell that needs it reads it, and corrupts the 'above' value too.
Explore the code comparisonHide the code comparison
Wrong sweep direction in the rolled array
Going right-to-left overwrites row[j-1] (the 'left') before the cell that needs it reads it, and corrupts the 'above' value too.
Don't write this
row = [1] * n
for _ in range(1, m):
for j in range(n - 1, 0, -1): # wrong direction
row[j] += row[j - 1]
return row[-1]Write this instead
row = [1] * n
for _ in range(1, m):
for j in range(1, n): # left to right
row[j] += row[j - 1]
return row[-1]3Factorial overflow in the closed form
(m+n-2)! grows astronomically even when C(m+n-2, m-1) is small, overflowing a long for moderate grids before any division happens.
Explore the code comparisonHide the code comparison
Factorial overflow in the closed form
(m+n-2)! grows astronomically even when C(m+n-2, m-1) is small, overflowing a long for moderate grids before any division happens.
Don't write this
long num = fact(m + n - 2);
long den = fact(m - 1) * fact(n - 1);
return (int)(num / den); // num overflowsWrite this instead
long result = 1;
int big = Math.max(m - 1, n - 1), k = Math.min(m - 1, n - 1);
for (int i = 1; i <= k; i++) result = result * (big + i) / i;
return (int) result;Revise
Carry the pattern into the interview
Pattern to remember
Grid DP — paths by additive recurrence
Code pattern to memorize
dp[i][j] = dp[i-1][j] + dp[i][j-1]
first row = first col = 1 # only one way along an edge
answer = dp[m-1][n-1]Rules to remember
- 1The recurrence is add the two cells you could have come from — up and left. Internalize the direction, not the indices.
- 2The entire first row and first column are 1: there is exactly one straight-line path along any edge. These are your base cases.
- 3You never need the full 2D table — each row only depends on the row above, so a single rolled 1D array collapses space to O(n).
- 4It's secretly combinatorics: you make exactly
m-1downs andn-1rights in some order, so the answer isC(m+n-2, m-1). - 5Build C(m+n-2, m-1) multiplicatively, not via factorials —
m+ncan overflow a naivefactoriallong before the answer does.
Use this pattern when
- Counting paths / ways through a grid with restricted moves (right/down)
- Each state depends only on a fixed set of *earlier* states — classic DP
- The question asks 'how many ways' rather than 'shortest' or 'is it possible'
- Moves are monotonic (you never go back), so there are no cycles to worry about
Choose another pattern when
- Grid has obstacles → still DP but obstacle cells force dp = 0 (Unique Paths II)
- You need the *shortest* weighted path → BFS/Dijkstra, not counting DP
- Moves can go in all four directions → cycles appear, counting DP breaks
- m and n are tiny but you need the *actual* paths listed → backtracking, not a count
Interview takeaway
Grid path-counting is the gateway DP: spot that a cell's answer is built from its neighbours and the recurrence writes itself. The same 'sum the cells I could have come from' move powers Minimum Path Sum, Unique Paths II, and Dungeon Game — and recognising the hidden combinatorics is what separates a strong answer from a memorised one.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternCanonical Grid DP — a cell's answer is built by combining its up/left neighbours. Recognise it whenever you count or optimise monotone paths through a grid; the same recurrence shape powers Minimum Path Sum, Unique Paths II, and Dungeon Game, and the obstacle-free case collapses to a binomial coefficient.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Unique Paths IIComing soonAdd obstacles — set dp = 0 on any blocked cell, keep the same up+left recurrence.
- Minimum Path SumSame grid shape, but take min(up, left) + cost instead of summing counts.
- Unique Paths IIIComing soonMust visit every empty cell exactly once — counting DP breaks, switch to backtracking.
- Dungeon GameComing soonGrid DP filled bottom-right to top-left because health constraints flow backwards.