Skip to main content

51. Unique Paths

mediumAsked at Plaid

Count the number of unique paths from top-left to bottom-right of an m x n grid, moving only right or down. Plaid asks this as a DP warm-up before harder grid-DP problems on transaction-state machines.

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

Source citations

Public interview reports confirming this problem appears in Plaid loops.

  • Glassdoor (2025)— Plaid intro DP screen.
  • LeetCode Discuss (2026)— Plaid SWE II OA.

Problem

There is a robot on an m x n grid. The robot is initially located at the top-left corner. The robot tries to move to the bottom-right corner. The robot 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
  • The answer is guaranteed to be <= 2 * 10^9.

Examples

Example 1

Input
m = 3, n = 7
Output
28

Example 2

Input
m = 3, n = 2
Output
3

Approaches

1. Recursive without memo

paths(i, j) = paths(i-1, j) + paths(i, j-1).

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

Tradeoff: Exponential. TLE.

2. 1D DP rolling row

Each row depends only on the row above. Use a single array of length n. dp[j] = dp[j] + dp[j-1].

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: O(m*n) time, O(n) space. The single-row rolling trick is the key optimization.

Plaid-specific tips

Plaid grades this on the space optimization from O(m*n) to O(n). Bonus signal: derive the recurrence dp[j] = dp[j] + dp[j-1] in place — the old dp[j] is the row above, and dp[j-1] is the cell to the left in the current row. Mention the closed-form C(m+n-2, m-1) as a stretch.

Common mistakes

  • Initializing dp[j] to 0 instead of 1 — first row and column should be all 1s.
  • Updating dp[j-1] from the right — corrupts the leftward read.
  • Off-by-one on the row/column count.

Follow-up questions

An interviewer at Plaid may pivot to one of these next:

  • With obstacles (LC 63).
  • Minimum path sum (LC 64).
  • Closed-form binomial: C(m+n-2, m-1).

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why O(n) instead of O(m*n)?

Each cell depends only on the cell above and the cell to the left. We can collapse the 'above' into a single rolling row.

Closed-form vs DP?

Closed-form is O(min(m, n)) using factorials, but BigInt for safety. DP is more general — easy to add obstacles or constraints. Plaid prefers DP for the interview.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →