Skip to main content

51. Unique Paths

mediumAsked at Workday

Count the number of unique paths from top-left to bottom-right of an m x n grid, moving only right or down. Workday uses this as a 2D DP intro — same shape as counting org-chart promotion paths through ranks.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2025)— Workday SDE2 phone screen.

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 the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

Constraints

  • 1 <= m, n <= 100
  • The answer is guaranteed to be less than or equal to 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

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

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

Tradeoff: Exponential.

2. 1D DP (rolling row)

Each cell = cell above + cell to left. Use a single row that updates in place.

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(n) space. dp[j] before the update is the cell above; dp[j-1] is the cell left.

Workday-specific tips

Workday loves the 1D-rolling optimization. Walk through why dp[j] alone suffices: when you update dp[j] += dp[j-1], the OLD dp[j] is the value from the previous row, and dp[j-1] is the already-updated current-row value. State this before coding.

Common mistakes

  • Using a 2D array when a 1D row works.
  • Initializing dp wrong — the first row and column are all 1s (only one path).
  • Off-by-one on grid dimensions.

Follow-up questions

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

  • Unique Paths II (LC 63) — with obstacles.
  • Combinatorial formula: C(m+n-2, m-1).
  • Unique Paths III (LC 980).

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 1D works?

Each cell depends only on cell above (same column, previous row) and cell left (previous column, current row). The 1D array holds the previous row going in, and the leftward value is current-row already updated.

Combinatorial?

Yes — total paths = C(m+n-2, m-1). Pure math, O(min(m, n)) time. Worth mentioning if interviewer asks for the closed form.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →