Skip to main content

51. Unique Paths

mediumAsked at Datadog

Count paths from top-left to bottom-right of an m x n grid, moving only right or down. Datadog asks this as a DP-fundamentals warmup before harder grid problems with constraints.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog phone screen DP question.

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. Brute-force recursion

f(r, c) = f(r-1, c) + f(r, c-1). Exponential without memo.

Time
O(2^(m+n))
Space
O(m+n)
function uniquePaths(m, n) {
  function f(r, c) {
    if (r === 0 || c === 0) return 1;
    return f(r - 1, c) + f(r, c - 1);
  }
  return f(m - 1, n - 1);
}

Tradeoff: Recomputes overlapping subproblems exponentially. Datadog will fail without memoization.

2. Bottom-up DP with rolling array (optimal)

dp[c] = paths to (current row, c). Update in place: dp[c] += dp[c-1].

Time
O(m * n)
Space
O(n)
function uniquePaths(m, n) {
  const dp = new Array(n).fill(1);
  for (let r = 1; r < m; r++) {
    for (let c = 1; c < n; c++) {
      dp[c] += dp[c - 1];
    }
  }
  return dp[n - 1];
}

Tradeoff: O(n) extra space. Datadog-canonical rolling-array DP trick — applicable wherever current state depends only on the previous row.

Datadog-specific tips

Datadog will probe with: 'Can you solve it without DP?' The answer is the combinatorial formula C(m+n-2, m-1) — directly compute the path count. Bonus signal: derive the formula and explain why it works.

Common mistakes

  • Initializing dp to 0 — needs to be 1 (one way to reach any cell in the first row).
  • Loop bounds — r starts at 1 because row 0 is the all-1 init.
  • Forgetting overflow — m=n=100 produces C(198, 99) which is huge; use BigInt if needed.

Follow-up questions

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

  • Unique Paths II (LC 63) — with obstacles.
  • Unique Paths III (LC 980) — backtracking with all-cells-visited constraint.
  • Combinatorial formula — 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 does the rolling array work?

DP[r][c] depends only on DP[r-1][c] (above) and DP[r][c-1] (left). When we update dp[c] in place, dp[c] holds the value from the previous row (the 'above'), and dp[c-1] holds the just-updated current row (the 'left'). Both are correct.

Combinatorial proof?

Any path is m-1 downs + n-1 rights in some order. The number of orderings is C(m+n-2, m-1).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →