Skip to main content

21. Unique Paths

mediumAsked at Ramp

Count distinct paths in an m x n grid moving only right or down.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

A robot is located at the top-left corner of an m x n grid. The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid. How many possible unique paths are there?

Constraints

  • 1 <= m, n <= 100
  • The answer fits in a 32-bit signed integer

Examples

Example 1

Input
m = 3, n = 7
Output
28

Example 2

Input
m = 3, n = 2
Output
3

Approaches

1. Brute-force recursion

Recurse on the two move choices without memoization.

Time
O(2^(m+n))
Space
O(m+n)
function uniquePaths(m, n) {
  function rec(i, j) {
    if (i === m - 1 || j === n - 1) return 1;
    return rec(i + 1, j) + rec(i, j + 1);
  }
  return rec(0, 0);
}

Tradeoff:

2. 1D DP rolling row

Each cell equals the count from above plus from the left; maintain only one row in place.

Time
O(m*n)
Space
O(n)
function uniquePaths(m, n) {
  const row = new Array(n).fill(1);
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      row[j] += row[j - 1];
    }
  }
  return row[n - 1];
}

Tradeoff:

Ramp-specific tips

Ramp likes the rolling-row trick because their approval-graph engine counts policy traversals in tight memory; demonstrating you can collapse a 2D DP to 1D is the bonus signal.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Unique Paths and other Ramp interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →