Skip to main content

52. Unique Paths

mediumAsked at Salesforce

Count unique paths in an m x n grid moving only right or down. Salesforce uses this as a canonical 2D DP problem.

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

Source citations

Public interview reports confirming this problem appears in Salesforce loops.

  • Glassdoor (2026-Q1)— Salesforce uses grid-DP variants for floor-plan navigation in their workplace app.
  • LeetCode Discuss (2025)— Common DP warmup.

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.

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). Exponential without memo.

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. Salesforce will dock you for not memoizing.

2. 2D DP with O(n) rolling row

Row-by-row: dp[j] = dp[j] + dp[j-1] (i.e., from above + from left).

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 by rolling rows. The trick: dp[j] (before update) is 'from above'; dp[j-1] (already updated) is 'from left'.

Salesforce-specific tips

Salesforce specifically tests the rolling-array space optimization. Bonus signal: mention the closed-form combinatorial solution C(m+n-2, m-1) which is O(min(m,n)) and feels like the 'real' answer once you spot the structure.

Common mistakes

  • Allocating an m*n 2D array — works but uses more memory than necessary.
  • Off-by-one in the loop bounds — must start at i=1, j=1 (the first row/col are all 1s).
  • Forgetting to initialize dp to 1s — the first row of a grid has exactly one path to each cell.

Follow-up questions

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

  • Unique Paths II (LC 63) — with obstacles.
  • Minimum Path Sum (LC 64) — grid with weights.
  • Closed-form via combinatorics.

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 initialize dp to 1s?

The first row has only one path to each cell (all right moves). The 1s represent that base case; the DP loop then fills in interior cells row by row.

Why is the closed-form C(m+n-2, m-1)?

Every path is a sequence of m-1 downs and n-1 rights. The number of orderings is the number of ways to choose which m-1 of m+n-2 positions are downs.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →