Skip to main content

21. Unique Paths

mediumAsked at Klarna

Count the number of unique paths from the top-left to bottom-right of an m x n grid, moving only right or down.

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

Problem

A robot is located at the top-left corner of an m x n grid. It can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner. How many possible unique paths are there?

Constraints

  • 1 <= m, n <= 100
  • Answer is guaranteed to fit in a 32-bit integer

Examples

Example 1

Input
m = 3, n = 7
Output
28

Example 2

Input
m = 3, n = 2
Output
3

Approaches

1. Recursive enumeration

Recurse from (0,0) trying right and down, base case at (m-1, n-1).

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

Tradeoff:

2. 1-D rolling DP

Each cell's count is the sum of the cell above and the cell to its left, so a single 1-D row updated in place suffices.

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

Tradeoff:

Klarna-specific tips

Klarna risk-feature engineers reach for the rolling-row trick on counting-style DPs because it matches how they collapse Markov-style payment-state grids in production scoring jobs.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →