#62 - Unique Paths

MediumDP - Multidimensional

A robot is at the top-left corner of an m × n grid. It can only move right or down. How many unique paths exist to reach the bottom-right corner?

Input	Output
m = 3, n = 7	28
m = 3, n = 2	3

Solution Space

Try it

/**
 * Counts unique paths from top-left to bottom-right of an m×n grid.
 * Uses a 1D rolling DP array: dp[j] += dp[j-1] at each row.
 *
 * @param m Number of rows
 * @param n Number of columns
 * @returns Number of unique paths
 */
export function uniquePaths(m: number, n: number): number {
  const dp = new Array<number>(n).fill(1);

  for (let row = 1; row < m; row++) {
    for (let col = 1; col < n; col++) {
      dp[col] += dp[col - 1];
    }
  }

  return dp[n - 1];
}

Approach: 1D rolling DP – first row is all 1s. For each subsequent row, `dp[col] = dp[col] (from above) + dp[col-1] (from left)`.

Time: O(m · n) – nested loops.

Space: O(n) – single row array.

Alternative approaches:

Approach	Idea	Time	Space
2D DP table	dp[i][j] = dp[i-1][j] + dp[i][j-1]	O(m · n)	O(m · n)
Combinatorics	Answer is C(m+n-2, m-1) = (m+n-2)! / ((m-1)! · (n-1)!)	O(m + n)	O(1)

Why the 1D DP approach is preferred: good balance of clarity and efficiency; combinatorics is O(1) space but risks integer overflow without careful implementation.

#1137 N-th Tribonacci Number

#72 Edit Distance