Skip to main content

53. Unique Paths

mediumAsked at Snowflake

Count unique paths from top-left to bottom-right in an m x n grid moving only right or down. Snowflake asks this as a 2D-DP warm-up and to set up a follow-up on space optimization with rolling rows.

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

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2025-Q4)— Snowflake new-grad onsite as DP warm-up.
  • LeetCode Discuss (2025-10)— Reported at Snowflake intern screens.

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

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 paths(i, j) {
    if (i === 0 || j === 0) return 1;
    return paths(i - 1, j) + paths(i, j - 1);
  }
  return paths(m - 1, n - 1);
}

Tradeoff: Exponential. Mention to reject.

2. 1D rolling DP (optimal)

dp[j] = ways to reach column j in the current row. Update in place row-by-row: 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] + dp[j - 1];
    }
  }
  return dp[n - 1];
}

Tradeoff: Linear scan per row, O(n) total state. Mention also the C(m+n-2, m-1) closed-form.

Snowflake-specific tips

Snowflake interviewers want the 1D rolling DP and the explanation that dp[j] (before update) is the previous row's value while dp[j-1] (after update) is the current row's value to the left. Bonus signal: mention the closed-form binomial coefficient as a sanity check, and discuss precision for large m, n.

Common mistakes

  • 2D DP allocating O(mn) — works but wastes memory.
  • Iterating in the wrong direction so dp[j-1] is from the previous row, not the current.
  • Off-by-one with initial row (must be all 1s).

Follow-up questions

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

  • Unique Paths II (LC 63) — with obstacles.
  • Closed-form binomial coefficient.
  • Memoization-based recursion.

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 does dp[j] = dp[j] + dp[j-1] work?

dp[j] before the update is the previous row's count at column j (= paths going DOWN). dp[j-1] is the current row's count to the left (= paths going RIGHT). Sum is the total.

Is the closed-form better?

Asymptotically yes (O(min(m,n))). But computing C(m+n-2, m-1) without overflow requires care. Most interviewers accept the DP version.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →