Unique Paths in TypeScript: From a Grid to One Row

A robot needs to cross a rectangular grid, moving only right or down. Finding one route is easy. Counting every possible route is where a small grid starts producing rather a lot of choices.
For LeetCode 62, Unique Paths, we only need that count. We don't need to draw the routes or keep a list of them. I'll build the answer one cell at a time, then show why the same calculation fits into a single row of storage.
Count the Ways to Arrive
Let m be the number of rows and n the number of columns. We start at the top‑left cell and finish at the bottom‑right. There are no obstacles, diagonal moves, or opportunities to go backwards.
Trying every sequence of moves would work on a tiny board, but many routes pass through the same cells. Repeating all the work beyond each arrival is unnecessary. The useful question is smaller: how many ways are there to reach this particular cell?
An interior cell has exactly two possible predecessors: the cell above it and the cell immediately to its left. Every route arrives through one of those two neighbours. Those groups cannot overlap, because a route has only one final move into the cell. Add their counts:
paths[row][column] = paths[row - 1][column] + paths[row][column - 1]
That is the recurrence. The table entry stores a count, rather than a route, a distance, or a flag saying whether we have visited the cell.
This distinction matters if you're coming from my Number of Islands walkthrough. There, marking a cell prevents us counting the same component twice. Here, several arrivals at a cell represent different valid paths, and their contributions must be added.
Give the Edges Somewhere to Start
There is only one way to reach any cell in the top row: keep moving right. Likewise, there is only one way to reach any cell in the first column: keep moving down. Every count along those two edges is therefore 1.
The starting cell also has count 1. That represents the single empty route: we are already there and have made no moves. Starting it at zero would quietly make every later answer zero. A robot with no options is one thing; a robot with no starting point is rather less useful.
These base cases already answer the narrow‑grid cases. A 1 × n grid has one route, as does an m × 1 grid. A 1 × 1 grid also returns 1.
Keep the Whole Table First
I prefer the full table whilst explaining the calculation. We can point at a cell and inspect exactly which two values produced it.
export const uniquePathsTable = (m: number, n: number): number => {
const paths = Array.from({ length: m }, () => new Array<number>(n).fill(1));
for (let row = 1; row < m; row += 1) {
for (let column = 1; column < n; column += 1) {
paths[row][column] = paths[row - 1][column] + paths[row][column - 1];
}
}
return paths[m - 1][n - 1];
};Initialising the whole table to ones keeps the setup short. Only the first row and first column retain those initial values; every interior entry is replaced before another calculation needs it. The loops move down the rows and left to right across each row, so both predecessors are ready.
The callback passed to Array.from creates a separate array for each row. Filling an outer array with the same inner array would make the rows share storage. Updating one row would then change the others, which is a fairly unhelpful shortcut.
Walk through a Three‑by‑Seven Grid
For m = 3 and n = 7, the completed table looks like this:
| Row | Column 0 | Column 1 | Column 2 | Column 3 | Column 4 | Column 5 | Column 6 |
|---|---|---|---|---|---|---|---|
| 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 2 | 1 | 3 | 6 | 10 | 15 | 21 | 28 |
The middle row grows steadily because every cell adds 1 from above. On the bottom row, column 2 gets 3 from above and 3 from the left, giving 6. Column 3 then gets 4 + 6 = 10.
At the destination, 7 routes arrive from above and 21 from the left. The answer is 28. We have counted them without constructing any of the routes themselves.
For the full‑table version, initialisation and traversal take O(m * n) time. The table also uses O(m * n) extra space. That is perfectly manageable within this problem's limits, but most of the stored rows are never read again.
Reuse the Row We Have Finished With
To calculate a cell, we need the value directly above it and the freshly calculated value to its left. We don't need the row above that. A single array can hold both pieces of information if we update it in the right order.
Just before updating paths[column], it still contains the previous row's count for that column. Meanwhile, paths[column - 1] already contains the current row's count to the left. Adding them overwrites the old value with the new one.
export const uniquePaths = (m: number, n: number): number => {
const width = Math.min(m, n);
const height = Math.max(m, n);
const paths = new Array<number>(width).fill(1);
for (let row = 1; row < height; row += 1) {
for (let column = 1; column < width; column += 1) {
paths[column] += paths[column - 1];
}
}
return paths[width - 1];
};The shorter dimension becomes the stored width. Swapping the dimensions preserves the answer: transposing each route swaps its right and down moves, giving a matching route in the transposed grid. There is no need to allocate the longer row.
For our 3 × 7 example, this version therefore works through seven rows of width three. Starting with [1, 1, 1], successive rows become [1, 2, 3], [1, 3, 6], [1, 4, 10], [1, 5, 15], [1, 6, 21], and finally [1, 7, 28].
The update must run left to right. Reversing it would read an old value on the left as well as above, so it would no longer implement the recurrence. With width three, the first new row would incorrectly end in 2 instead of 3.
Time remains O(m * n), and extra space becomes O(min(m, n)). Both functions receive dimensions rather than a caller‑owned grid, so neither modifies any input data.
Why a JavaScript Number is Enough Here
The official constraints require integer dimensions between 1 and 100, and generated cases have an answer no larger than 2,000,000,000. Both conditions matter. A 100 × 100 grid satisfies the dimension limits but not the answer guarantee.
JavaScript's safe integer range extends to 2^53 - 1, comfortably beyond that guaranteed answer. Our intermediate counts are safe too: counts never decrease as we move right or down, and each cell's count is at most the destination's count. Each addition therefore produces another exact integer within the same bound.
The snippets assume those stated inputs. They do not validate zero, fractional, or negative dimensions, or promise exact answers for unrestricted grids. For a larger counting problem, I would revisit the numeric representation rather than assume the dimension limit alone makes number safe.
Test the Counting, Not Just the Example
Useful checks include (1, 1) → 1, (1, 100) → 1, (100, 1) → 1, (2, 2) → 2, and (3, 7) → 28. Swapping the dimensions should preserve every result. Comparing the table and rolling versions also helps expose an incorrect update direction.
For an independent check, a route contains m - 1 down moves amongst m + n - 2 total moves. Choosing their positions gives the binomial coefficient C(m + n - 2, m - 1). My tests calculate that with BigInt, using exact integer multiplication and division, rather than factorials or floating‑point rounding.
My Dynamic Programming Comparison Lab includes both implementations and those exact‑count checks. You can run every dimension pair within the challenge's full constraints, then deliberately reverse the rolling loop and see which small grids expose the mistake. The article's table gives you something concrete to compare with the failing result.
The Part to Keep
The key decision is what each stored value means. Once a cell holds the number of ways to reach it, the two possible final moves give us the recurrence, and the edges give us the starting values. Reducing the storage then becomes a question of which earlier results are still needed.
For another example of making that choice, my Coin Change walkthrough stores the fewest coins needed for each amount. The state has a different meaning, so it combines earlier answers differently. Getting that meaning clear is more useful than memorising the loop.