A robot sits in the top-left cell of an m × n grid. It wants to reach the bottom-right cell, and it can only ever step one cell right or one cell down — never up, left, or diagonally. Your job is to count how many distinct routes it can take. This is the classic Unique Paths lattice-path problem.
// m = number of rows, n = number of columns. Both are >= 1.
// Returns the count of distinct right/down paths from top-left to bottom-right.
function gridDistinctPaths(m: number, n: number): number;gridDistinctPaths(3, 7); // 28
// A 3-row, 7-column grid has 28 distinct right/down routes.
gridDistinctPaths(3, 2); // 3
// Down-Down-Right, Down-Right-Down, Right-Down-Down.gridDistinctPaths(1, 5); // 1 — only one row: go right every time
gridDistinctPaths(2, 2); // 2 — Right-Down or Down-Right(m - 1) + (n - 1) steps.m === 1 or n === 1 there is no choice to make — the robot walks straight to the corner. gridDistinctPaths(1, n) and gridDistinctPaths(m, 1) both return 1.0 or negative inputs.You'll count every right/down route a robot can take across a grid by filling a table where each cell records how many ways there are to reach it.
A robot starts in the top-left cell of an m × n grid and wants the bottom-right cell. It can only step right or down. How many distinct routes are there? Picture a small 3-row, 4-column grid: some routes hug the top edge then drop down the right side, others zig-zag through the middle. Each one is a different sequence of moves, and we want the total count — not the routes themselves.
The key observation that unlocks everything: every path has exactly (m - 1) down-steps and (n - 1) right-steps, in some order. The robot never moves up or left, so it can never revisit a cell.
Ask a smaller question first: how many ways are there to reach one particular cell? To stand on a cell, the robot's last move was either a step down from the cell directly above, or a step right from the cell directly to the left. Those are the only two ways in. So the number of ways to reach a cell is the number of ways to reach the cell above it, plus the number of ways to reach the cell on its left.
That gives the recurrence dp[i][j] = dp[i-1][j] + dp[i][j-1]. The cells on the top row and the left column are special: there's only one straight-line way to reach them (keep going right, or keep going down), so they're all 1. The answer is whatever lands in the bottom-right cell.
The recurrence is naturally recursive, so the most direct version just translates it line for line. Count the paths to a cell (i, j) measured from the bottom-right corner, where i rows and j columns still remain to cross:
function gridDistinctPaths(m, n) {
// Base case: a single row or single column has exactly one path.
if (m === 1 || n === 1) return 1;
// Last move into this cell came from above OR from the left.
return gridDistinctPaths(m - 1, n) + gridDistinctPaths(m, n - 1);
}This returns the right answer — gridDistinctPaths(3, 7) really does give 28. The problem is speed. The function calls itself twice on almost every invocation, and the two branches overlap heavily: reaching the same interior cell shows up in many different ways down the call tree, and each time we recompute its entire subtree from scratch. The number of calls grows roughly like the number of paths itself, which is exponential. By the time you ask for a grid like gridDistinctPaths(20, 20) it makes hundreds of millions of calls and effectively hangs.
The fix is to compute each cell's value exactly once and store it. We fill a table row by row, left to right — and because each cell only ever looks at the cell above and the cell to its left, we don't even need the full 2D table. A single row of length n is enough: before we overwrite row[j], it still holds the value from the row above (dp[i-1][j]), and row[j-1] already holds this row's freshly-computed value to the left (dp[i][j-1]). Adding them in place gives the new cell.
function gridDistinctPaths(m, n) {
// The top row of the grid: every cell is reachable exactly one way
// (keep moving right), so the row starts as all 1s.
const row = new Array(n).fill(1);
// Process each remaining grid row, updating `row` in place.
for (let i = 1; i < m; i++) {
// Left to right: row[j-1] is already THIS row's value (the cell to the
// left), while row[j] still holds the row above (the cell up top).
for (let j = 1; j < n; j++) {
row[j] += row[j - 1]; // dp[i][j] = dp[i-1][j] + dp[i][j-1]
}
// row[0] stays 1: the whole left column is reachable only one way.
}
// The bottom-right cell is the last slot after the final row sweep.
return row[n - 1];
}
module.exports = { gridDistinctPaths };Three shifts turn the exponential recursion into linear work. First, we store results instead of recomputing them, so each cell is touched once. Second, we iterate bottom-up — filling the base row first, then building each row from the one before — which removes the recursion entirely. Third, we roll the 2D table down to one row, because a cell only depends on its immediate neighbours above and to the left, so the rows further up are dead weight. The result runs in O(m × n) time and O(n) space.
Trace gridDistinctPaths(3, 4) — three rows, four columns. The answer should be 10.
start row = [1, 1, 1, 1] ← the top grid row: all 1s
i = 1 (second grid row), sweep j = 1..3:
j=1 row[1] += row[0] = 1 + 1 = 2 → [1, 2, 1, 1]
j=2 row[2] += row[1] = 1 + 2 = 3 → [1, 2, 3, 1]
j=3 row[3] += row[2] = 1 + 3 = 4 → [1, 2, 3, 4]
i = 2 (third grid row), sweep j = 1..3:
j=1 row[1] += row[0] = 2 + 1 = 3 → [1, 3, 3, 4]
j=2 row[2] += row[1] = 3 + 3 = 6 → [1, 3, 6, 4]
j=3 row[3] += row[2] = 4 + 6 = 10 → [1, 3, 6, 10]
return row[3] = 10
Notice the final array [1, 3, 6, 10] is exactly the bottom row of the 2D table in the mental-model diagram. At j=3 in the last sweep, row[3] was still 4 (the value from the row above, dp[1][3]) and row[2] had just become 6 (this row's left neighbour, dp[2][2]). Adding them gives 10 — "above plus left," computed with one array instead of a whole grid.
0 forever — there's no base case to build on. The cells reachable in exactly one way (m === 1 or n === 1, and the grid's first row and first column) are the seeds the whole recurrence grows from. Fill the starting row with 1s and never touch row[0].gridDistinctPaths(2, 2) (and every other shared subproblem) once per path through it. If you keep the recursion, add memoization — cache results in a Map keyed by `${m},${n}` — to collapse the exponential tree back to O(m × n).row[j] += row[j - 1] needs row[j - 1] to already be this row's value. Iterate right to left and row[j-1] is still the previous row's value, and your counts come out wrong. (This is the opposite of 0/1-knapsack's right-to-left sweep — don't carry the habit over.)m and n. m is rows (the outer loop), n is columns (the row length and inner loop). Swap them and a 3 × 7 grid silently becomes 7 × 3. The count is the same here by symmetry, so the bug hides — but you'll allocate the wrong-length array and read past the end on non-square inputs if you mix the roles. Keep row of length n, loop i to m.row[n - 1]. Returning row[0] (always 1) or reading before the last i iteration gives a wrong, smaller number.20 × 20 grid has over 35 billion paths), but JavaScript numbers stay exact integers up to 2^53, which covers every grid in the test suite. For truly huge grids you'd reach for BigInt; that's out of scope.(m - 1) downs and (n - 1) rights, so counting paths is counting the ways to choose which of the (m + n - 2) total steps are the downs: C(m + n - 2, m - 1). For 3 × 7 that's C(8, 2) = 28. Computed with a running product it's O(min(m, n)) time and O(1) space — faster than the DP, at the cost of being less obviously correct and needing care to avoid intermediate overflow.0 ways, so set row[j] = 0 whenever cell (i, j) is an obstacle instead of adding. The top row and left column are no longer all 1 either — once you hit a wall along an edge, every cell past it on that edge becomes unreachable.a × b × c box, stepping only along positive axes, generalizes the recurrence to summing the three predecessor cells. The closed form generalizes too, into a multinomial coefficient (a + b + c - 3)! / ((a-1)! (b-1)! (c-1)!). The rolling-array trick still applies — you roll away one dimension and keep a 2D slab in memory.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.
A robot sits in the top-left cell of an m × n grid. It wants to reach the bottom-right cell, and it can only ever step one cell right or one cell down — never up, left, or diagonally. Your job is to count how many distinct routes it can take. This is the classic Unique Paths lattice-path problem.
// m = number of rows, n = number of columns. Both are >= 1.
// Returns the count of distinct right/down paths from top-left to bottom-right.
function gridDistinctPaths(m: number, n: number): number;gridDistinctPaths(3, 7); // 28
// A 3-row, 7-column grid has 28 distinct right/down routes.
gridDistinctPaths(3, 2); // 3
// Down-Down-Right, Down-Right-Down, Right-Down-Down.gridDistinctPaths(1, 5); // 1 — only one row: go right every time
gridDistinctPaths(2, 2); // 2 — Right-Down or Down-Right(m - 1) + (n - 1) steps.m === 1 or n === 1 there is no choice to make — the robot walks straight to the corner. gridDistinctPaths(1, n) and gridDistinctPaths(m, 1) both return 1.0 or negative inputs.You'll count every right/down route a robot can take across a grid by filling a table where each cell records how many ways there are to reach it.
A robot starts in the top-left cell of an m × n grid and wants the bottom-right cell. It can only step right or down. How many distinct routes are there? Picture a small 3-row, 4-column grid: some routes hug the top edge then drop down the right side, others zig-zag through the middle. Each one is a different sequence of moves, and we want the total count — not the routes themselves.
The key observation that unlocks everything: every path has exactly (m - 1) down-steps and (n - 1) right-steps, in some order. The robot never moves up or left, so it can never revisit a cell.
Ask a smaller question first: how many ways are there to reach one particular cell? To stand on a cell, the robot's last move was either a step down from the cell directly above, or a step right from the cell directly to the left. Those are the only two ways in. So the number of ways to reach a cell is the number of ways to reach the cell above it, plus the number of ways to reach the cell on its left.
That gives the recurrence dp[i][j] = dp[i-1][j] + dp[i][j-1]. The cells on the top row and the left column are special: there's only one straight-line way to reach them (keep going right, or keep going down), so they're all 1. The answer is whatever lands in the bottom-right cell.
The recurrence is naturally recursive, so the most direct version just translates it line for line. Count the paths to a cell (i, j) measured from the bottom-right corner, where i rows and j columns still remain to cross:
function gridDistinctPaths(m, n) {
// Base case: a single row or single column has exactly one path.
if (m === 1 || n === 1) return 1;
// Last move into this cell came from above OR from the left.
return gridDistinctPaths(m - 1, n) + gridDistinctPaths(m, n - 1);
}This returns the right answer — gridDistinctPaths(3, 7) really does give 28. The problem is speed. The function calls itself twice on almost every invocation, and the two branches overlap heavily: reaching the same interior cell shows up in many different ways down the call tree, and each time we recompute its entire subtree from scratch. The number of calls grows roughly like the number of paths itself, which is exponential. By the time you ask for a grid like gridDistinctPaths(20, 20) it makes hundreds of millions of calls and effectively hangs.
The fix is to compute each cell's value exactly once and store it. We fill a table row by row, left to right — and because each cell only ever looks at the cell above and the cell to its left, we don't even need the full 2D table. A single row of length n is enough: before we overwrite row[j], it still holds the value from the row above (dp[i-1][j]), and row[j-1] already holds this row's freshly-computed value to the left (dp[i][j-1]). Adding them in place gives the new cell.
function gridDistinctPaths(m, n) {
// The top row of the grid: every cell is reachable exactly one way
// (keep moving right), so the row starts as all 1s.
const row = new Array(n).fill(1);
// Process each remaining grid row, updating `row` in place.
for (let i = 1; i < m; i++) {
// Left to right: row[j-1] is already THIS row's value (the cell to the
// left), while row[j] still holds the row above (the cell up top).
for (let j = 1; j < n; j++) {
row[j] += row[j - 1]; // dp[i][j] = dp[i-1][j] + dp[i][j-1]
}
// row[0] stays 1: the whole left column is reachable only one way.
}
// The bottom-right cell is the last slot after the final row sweep.
return row[n - 1];
}
module.exports = { gridDistinctPaths };Three shifts turn the exponential recursion into linear work. First, we store results instead of recomputing them, so each cell is touched once. Second, we iterate bottom-up — filling the base row first, then building each row from the one before — which removes the recursion entirely. Third, we roll the 2D table down to one row, because a cell only depends on its immediate neighbours above and to the left, so the rows further up are dead weight. The result runs in O(m × n) time and O(n) space.
Trace gridDistinctPaths(3, 4) — three rows, four columns. The answer should be 10.
start row = [1, 1, 1, 1] ← the top grid row: all 1s
i = 1 (second grid row), sweep j = 1..3:
j=1 row[1] += row[0] = 1 + 1 = 2 → [1, 2, 1, 1]
j=2 row[2] += row[1] = 1 + 2 = 3 → [1, 2, 3, 1]
j=3 row[3] += row[2] = 1 + 3 = 4 → [1, 2, 3, 4]
i = 2 (third grid row), sweep j = 1..3:
j=1 row[1] += row[0] = 2 + 1 = 3 → [1, 3, 3, 4]
j=2 row[2] += row[1] = 3 + 3 = 6 → [1, 3, 6, 4]
j=3 row[3] += row[2] = 4 + 6 = 10 → [1, 3, 6, 10]
return row[3] = 10
Notice the final array [1, 3, 6, 10] is exactly the bottom row of the 2D table in the mental-model diagram. At j=3 in the last sweep, row[3] was still 4 (the value from the row above, dp[1][3]) and row[2] had just become 6 (this row's left neighbour, dp[2][2]). Adding them gives 10 — "above plus left," computed with one array instead of a whole grid.
0 forever — there's no base case to build on. The cells reachable in exactly one way (m === 1 or n === 1, and the grid's first row and first column) are the seeds the whole recurrence grows from. Fill the starting row with 1s and never touch row[0].gridDistinctPaths(2, 2) (and every other shared subproblem) once per path through it. If you keep the recursion, add memoization — cache results in a Map keyed by `${m},${n}` — to collapse the exponential tree back to O(m × n).row[j] += row[j - 1] needs row[j - 1] to already be this row's value. Iterate right to left and row[j-1] is still the previous row's value, and your counts come out wrong. (This is the opposite of 0/1-knapsack's right-to-left sweep — don't carry the habit over.)m and n. m is rows (the outer loop), n is columns (the row length and inner loop). Swap them and a 3 × 7 grid silently becomes 7 × 3. The count is the same here by symmetry, so the bug hides — but you'll allocate the wrong-length array and read past the end on non-square inputs if you mix the roles. Keep row of length n, loop i to m.row[n - 1]. Returning row[0] (always 1) or reading before the last i iteration gives a wrong, smaller number.20 × 20 grid has over 35 billion paths), but JavaScript numbers stay exact integers up to 2^53, which covers every grid in the test suite. For truly huge grids you'd reach for BigInt; that's out of scope.(m - 1) downs and (n - 1) rights, so counting paths is counting the ways to choose which of the (m + n - 2) total steps are the downs: C(m + n - 2, m - 1). For 3 × 7 that's C(8, 2) = 28. Computed with a running product it's O(min(m, n)) time and O(1) space — faster than the DP, at the cost of being less obviously correct and needing care to avoid intermediate overflow.0 ways, so set row[j] = 0 whenever cell (i, j) is an obstacle instead of adding. The top row and left column are no longer all 1 either — once you hit a wall along an edge, every cell past it on that edge becomes unreachable.a × b × c box, stepping only along positive axes, generalizes the recurrence to summing the three predecessor cells. The closed form generalizes too, into a multinomial coefficient (a + b + c - 3)! / ((a-1)! (b-1)! (c-1)!). The rolling-array trick still applies — you roll away one dimension and keep a 2D slab in memory.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.