Skip to main content

20. Unique Paths

mediumAsked at Adobe

Count the number of unique paths in an m×n grid from the top-left to the bottom-right moving only right or down. Adobe uses this to assess dynamic programming fluency and the candidate's ability to reduce a combinatorial problem to a grid DP — skills that transfer to rendering pipeline optimization and layout engine design.

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

Source citations

Public interview reports confirming this problem appears in Adobe loops.

  • LeetCode Discuss (2025-09)— Adobe candidates report DP grid problems as a standard category in SDE-II interviews.
  • Glassdoor (2026-01)— Adobe onsite reports mention grid DP problems alongside 2D array manipulation themes.

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 will 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

Explanation: Three paths: Right-Down-Down, Down-Right-Down, Down-Down-Right.

Approaches

1. Recursive with memoization (top-down DP)

Recursively compute paths(i, j) = paths(i-1, j) + paths(i, j-1) with a memo map.

Time
O(m*n)
Space
O(m*n)
function uniquePaths(m, n) {
  const memo = new Map();
  function dp(r, c) {
    if (r === 1 || c === 1) return 1;
    const key = `${r},${c}`;
    if (memo.has(key)) return memo.get(key);
    const result = dp(r - 1, c) + dp(r, c - 1);
    memo.set(key, result);
    return result;
  }
  return dp(m, n);
}

Tradeoff: Correct and O(m*n) time/space; Adobe will ask for the bottom-up version and then the O(n) space optimization.

2. Bottom-up DP with O(n) space

Fill a 1D dp array of length n, where dp[j] = number of ways to reach column j in the current row. dp[j] += dp[j-1] for each row. The key insight: only the previous row and current column are needed, so a single row suffices.

Time
O(m*n)
Space
O(n)
function uniquePaths(m, n) {
  const dp = 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 1D rolling array is the expected optimization. The top row and leftmost column are always 1 (only one path along edges), so initializing with all 1s is correct.

Adobe-specific tips

Adobe interviewers value the combinatorial insight: the answer is C(m+n-2, m-1) — choose which m-1 of the m+n-2 moves are 'down'. Mentioning this mathematical closed form (with the caveat of overflow risk for large inputs) signals strong problem-solving depth. Follow up with Unique Paths II (LC 63) which adds obstacle cells.

Common mistakes

  • Initializing the dp array to 0 instead of 1 — the first row and column each have exactly one path.
  • Running the outer loop from 0 instead of 1, causing the first row to be overwritten.
  • Forgetting that this is 1-indexed conceptually — confusing row index with m.

Follow-up questions

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

  • Unique Paths II (LC 63): grid has obstacles — some cells are blocked.
  • Minimum Path Sum (LC 64): minimize the sum of values along the path.
  • Can you solve this in O(min(m,n)) space? (Use the smaller dimension for the rolling array.)

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 is dp initialized to all 1s?

The top row and leftmost column each have exactly one path (you can only go right along the top row and only go down along the left column). Initializing to 1 captures this base case.

How does the combinatorial formula C(m+n-2, m-1) work?

Every path requires exactly m-1 moves down and n-1 moves right, for a total of m+n-2 moves. Choosing which m-1 of those are 'down' uniquely determines the path, giving C(m+n-2, m-1) paths.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →