Skip to main content

18. Unique Paths

mediumAsked at Revolut

Count distinct lattice paths from top-left to bottom-right of a grid using DP, a Revolut warmup that mirrors counting valid FX-conversion routes between two currencies through intermediate hubs.

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

Problem

Given m and n, a robot at the top-left corner of an m x n grid wants to reach the bottom-right. It may move only right or down. Return the number of distinct paths.

Constraints

  • 1 <= m, n <= 100
  • 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. Recursive count

Recurse on (i-1,j) + (i,j-1) without memo.

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

Tradeoff:

2. 1D DP rolling row

Iterate row by row, keeping one row of size n; each cell adds the cell to its left. Linear in m*n time, O(n) space.

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:

Revolut-specific tips

Revolut likes you to mention the binomial-coefficient closed form C(m+n-2, m-1) as an even faster alternative — they value candidates who notice combinatorial shortcuts in FX-routing problems.

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

Practice these live with InterviewChamp.AI →