unique-paths.ts

/**
 * 62. Unique Paths  (Medium)
 * Link: https://leetcode.com/problems/unique-paths/
 *
 * A robot starts at the top-left of an m x n grid and can only move right or
 * down. Return the number of distinct paths to the bottom-right corner.
 *
 * Example:
 *   Input:  m = 3, n = 7
 *   Output: 28
 *
 * Approach:
 *   DP: paths to a cell = paths from above + paths from the left. The first row
 *   and column are all 1 (single straight path). We compress the table to one
 *   row, updating in place: row[j] += row[j-1].
 *
 * Time:  O(m * n)
 * Space: O(n)
 */
export function uniquePaths(m: number, n: number): number {
  const row = new Array<number>(n).fill(1);

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

  return row[n - 1];
}