Unique Paths

Medium
95.

Unique Paths

Unique Paths is a medium coding problem on dynamic programming, math and combinatorics, asked in Ola and Razorpay interviews.

A robot starts at the top-left corner of an m x n grid and only moves right or down, aiming for the bottom-right corner.

Return the number of unique paths.

Example 1

Input
m = 3, n = 7
Output
28

Example 2

Input
m = 3, n = 2
Output
3
Explanation
Right→Down→Down, Down→Down→Right, Down→Right→Down.

Constraints

  • 1 <= m, n <= 12
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Unique Paths — Solution in Python, Java & C++

Unique Paths solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Ola and Razorpay.

Unique Paths is a medium coding problem on dynamic programming, math and combinatorics, asked in Ola and Razorpay interviews.

Problem statement

A robot starts at the top-left corner of an m x n grid and only moves right or down, aiming for the bottom-right corner.

Return the number of unique paths.

Example 1

Input: m = 3, n = 7
Output: 28

Example 2

Input: m = 3, n = 2
Output: 3
Explanation: Right→Down→Down, Down→Down→Right, Down→Right→Down.

Constraints

  • 1 <= m, n <= 12

Hints for Unique Paths

  1. Hint 1

    paths(i,j) = paths(i-1,j) + paths(i,j-1); the edges have exactly one path.

  2. Hint 2

    It's also the binomial coefficient C(m+n-2, m-1).

How to solve Unique Paths

The robot reaches a cell only from directly above or directly to its left, so the number of paths to a cell is the sum of the paths to those two neighbours. The top row and left column each have exactly one path (straight along the edge), and filling the grid row by row gives the answer.

Approach

  1. Every cell in the first row and first column has exactly 1 path.
  2. For every other cell, paths[i][j] = paths[i-1][j] + paths[i][j-1].
  3. Fill row by row so both predecessors are ready when needed.
  4. Only the previous row matters, so a single array of width n suffices — row[j] += row[j-1] updates in place.

Why it works

Each path arrives by a unique final move, from above or from the left, so the two sets of paths are disjoint and together exhaust every possibility — the sum is exact. The rolling-array trick works because when you reach row[j], it still holds the value from the row above (the paths[i-1][j] term) while row[j-1] has already been updated for the current row (the paths[i][j-1] term). Combinatorially the answer is C(m+n-2, m-1), choosing which of the moves go down.

Complexity

  • Time — O(m · n)
  • Space — O(n)

Pitfalls

  • Seed the first row and column to 1, not 0.
  • With the rolling array, sweep j left to right — the in-place update depends on that order.
  • A single row or column has exactly one path, which the seeding handles.
  • The closed-form binomial is exact but needs care to avoid overflow in the intermediate factorials.

Reference solution

Python

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

Java

public static 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++) row[j] += row[j - 1];
    }
    return row[n - 1];
}

C++

int uniquePaths(int m, int n) {
    vector<int> row(n, 1);
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) row[j] += row[j - 1];
    }
    return row[n - 1];
}

JavaScript

var uniquePaths = function(m, n) {
    const dp = new Array(n).fill(1);
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) dp[j] += dp[j - 1];
    }
    return dp[n - 1];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 402 dynamic programming problems · the whole catalogue

Learn the technique: Dynamic Programming