Skip to main content

20. Unique Paths

mediumAsked at Wise

Count grid paths from top-left to bottom-right moving only right or down — Wise frames it as counting candidate FX routes through their corridor graph.

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

Problem

An m x n grid has a robot at the top-left corner that may only move right or down. Return the number of unique paths the robot can take to reach the bottom-right corner.

Constraints

  • 1 <= m, n <= 100
  • Answer fits in a 32-bit integer
  • Movement restricted to right or down

Examples

Example 1

Input
m=3, n=7
Output
28

Example 2

Input
m=3, n=2
Output
3

Approaches

1. Naive recursion

Recurse f(i,j) = f(i-1,j) + f(i,j-1) with no 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);
}
return f(m-1,n-1);

Tradeoff:

2. 1D DP roll

Roll a single row; dp[j] becomes dp[j] + dp[j-1] for each row. Constant rows of memory, O(m*n) work.

Time
O(m*n)
Space
O(n)
function uniquePaths(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] + dp[j - 1];
    }
  }
  return dp[n - 1];
}

Tradeoff:

Wise-specific tips

Wise loves the rolled-array DP here because their corridor routing precomputes feasible legs the same way — a single buffer reused across rows, never an m*n allocation.

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

Practice these live with InterviewChamp.AI →