Unique Paths

Medium15–20 min

Topics

Dynamic ProgrammingMatrix

Companies

AmazonGoogleBloomberg

Given the dimensions of a grid, starting at the top-left corner and only ever able to move one step right or one step down, count how many distinct paths reach the bottom-right corner. Every cell's answer depends only on the two cells that could lead into it: the one directly above (reached by moving down into this cell) and the one directly to its left (reached by moving right into this cell). The number of paths through this cell is simply the sum of the paths that could arrive from each of those two directions, and the very first row and first column each have only one possible path — a straight line along the edge — since there's no cell above or to the left of them to arrive from. Filling in the grid this way, one row at a time from the top-left corner onward, builds up to the total path count at the bottom-right corner.

Test Case 1:

Input:m = 3, n = 4

Output:10

Explanation:A 3-row, 4-column grid has 10 distinct right/down paths from the top-left corner to the bottom-right corner.

Test Case 2:

Input:m = 4, n = 5

Output:35

Explanation:A 4-row, 5-column grid has 35 distinct right/down paths.

Test Case 3:

Input:m = 1, n = 6

Output:1

Explanation:With only one row, the only path is moving right the whole way — exactly 1 way.

Constraints

◆1 ≤ m, n ≤ 100

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Recursive Without Memoization

Brute

Standing on any cell, the only two legal moves are one step down or one step right, so the number of ways to reach the bottom-right corner from that cell is just the number of ways from moving down plus the number of ways from moving right. Reaching the bottom-right corner itself counts as one complete path; stepping off the bottom or right edge of the grid is not a valid move and contributes nothing. Starting the recursion at the top-left corner and exploring every down/right choice at every cell counts every distinct path, though the same cell ends up being visited — and its sub-count recomputed — along many different paths.

TimeO(2^(m+n))

SpaceO(m + n)

Java

Try it out

class Solution {
    private int m;
    private int n;

    public int uniquePaths(int m, int n) {
        this.m = m;
        this.n = n;
        return solve(0, 0);
    }

    private int solve(int i, int j) {
        if (i == m - 1 && j == n - 1) return 1;
        if (i >= m || j >= n) return 0;
        return solve(i + 1, j) + solve(i, j + 1);
    }
}

Optimal — Bottom-Up 1D DP

Optimal

Track, for the row currently being processed, the number of ways to reach each column from the top-left corner. Every cell in the very first row only has one way to be reached — moving right the whole way — so that row starts as all 1s. For every later row, the count at a column is the count already sitting there from the row above (arriving by moving down) plus the count just computed at the column to its left in this same row (arriving by moving right) — and since the array is updated left to right, that left-neighbor value is already the current row's, not the row above's. After sweeping through every row, the last column holds the total number of paths.

TimeO(m × n)

SpaceO(n)