Skip to main content

53. Unique Paths

mediumAsked at Ola

Count distinct paths from the top-left to the bottom-right of an m x n grid moving only right or down.

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

Problem

There is a robot on an m x n grid. The robot is initially located at the top-left corner and tries to move to the bottom-right corner. The robot can only move either down or right at any point. Return the number of possible unique paths.

Constraints

  • 1 <= m, n <= 100

Examples

Example 1

Input
m = 3, n = 7
Output
28

Example 2

Input
m = 3, n = 2
Output
3

Approaches

1. Recursive try every move

Recurse from (0,0); base case at the corner.

Time
O(2^(m+n))
Space
O(m+n)
const f = (r,c) => r===m-1 && c===n-1 ? 1 : (r>=m || c>=n ? 0 : f(r+1,c) + f(r,c+1));
return f(0,0);

Tradeoff:

2. 1D rolling DP

Keep one row; each cell becomes itself + previous. Final cell is the answer.

Time
O(m*n)
Space
O(n)
function uniquePaths(m, n) {
  const dp = 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];
}

Tradeoff:

Ola-specific tips

Ola uses this to verify DP intuition; tie it to counting alternative dispatch routes between a pickup and a drop-off on a constrained grid.

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 Ola interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →