Skip to main content

20. Unique Paths

mediumAsked at SoFi

Count the number of distinct paths from top-left to bottom-right in an m x n grid moving only right or down — SoFi uses this DP warm-up because it's structurally identical to counting investment-portfolio rebalancing paths.

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

Problem

There is a robot on an m x n grid. The robot starts at the top-left corner and tries to reach the bottom-right corner. It can only move either down or right at any point in time. Given m and n, 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. Brute force recursion

Recurse on (i, j) reaching (m-1, n-1) — exponential without memoization.

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

Tradeoff:

2. Bottom-up DP

dp[i][j] = dp[i-1][j] + dp[i][j-1] with the first row and column initialized to 1. Can be optimized to 1D row.

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-1];
    }
  }
  return dp[n-1];
}

Tradeoff:

SoFi-specific tips

SoFi grades on whether you optimize the 2D DP table to a 1D rolling array — investment rebalancing paths over thousands of accounts must fit in cache, so space-efficient DP is a real win 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 SoFi interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →