MediumMathDynamic ProgrammingCombinatorics

Unique Paths

1 approach, code in every language

A robot starts in the top-left cell of an m x n grid. At every move it may step only one cell to the right or one cell down, and it is trying to reach the bottom-right cell.

Return how many distinct paths the robot can take to travel from the top-left corner to the bottom-right corner.

Example 1

Input: m = 3, n = 7

Output: 28

There are 28 unique right/down routes across a 3 by 7 grid.

Example 2

Input: m = 3, n = 2

Output: 3

From the top-left the robot can reach the bottom-right corner in exactly three ways.

Constraints

1 <= m, n <= 100

1D Row Compression

Fill a grid where each cell sums the paths from above and from the left, compressed into a single reusable row.

Loading animation…

Intuition

Any path into cell (i, j) arrives either from the cell directly above or the cell directly to its left, so dp[i][j] = dp[i-1][j] + dp[i][j-1], with the entire first row and first column equal to 1. Computing rows top to bottom, the value we need from above is exactly the value currently stored in the same column of a single row buffer before we overwrite it. That lets us collapse the 2D table into one array of length n. Purely combinatorially the count equals C(m+n-2, m-1), since any path is a fixed arrangement of (m-1) downs among (m+n-2) total moves. The DP version avoids large factorials and overflow concerns while running in linear space. We update the row in place from left to right, accumulating contributions from the left neighbor.

Algorithm walkthrough

1Create a row array of length n filled with 1s, representing the topmost row where every cell has a single path.
2For each subsequent row i from 1 to m-1, process columns left to right.
3For column j from 1 onward, add the left neighbor into the current cell: row[j] += row[j-1].
4Before the update, row[j] still holds the value from the row above, and row[j-1] holds the freshly computed left value, so the sum matches dp[i-1][j] + dp[i][j-1].
5Leave row[0] untouched since the first column always has exactly one path.
6After all rows are processed, row[n-1] is the number of unique paths.

Implementation

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        row = [1] * n
        for _ in range(1, m):
            for j in range(1, n):
                row[j] += row[j - 1]
        return row[n - 1]

Time

O(m * n)

Space

O(n)

Every cell is touched once; a single row of length n replaces the full table. The closed form C(m+n-2, m-1) can answer in O(min(m, n)) if factorial overflow is managed.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Dynamic Programming

After the pattern

Now solve one you haven't seen.

Grid Courier Routes is our own problem on the technique behind Unique Paths: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free