Unique Paths

Medium

Problem

A robot starts at the top-left of an m × n grid and moves only right or down. Return the number of distinct paths to the bottom-right corner.

Example 1

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

Example 2

Input:  m = 3, n = 2
Output: 3

Test cases

Case 1

Input:    3, 7
Expected: 28

Case 2

Input:    3, 2
Expected: 3

Case 3

Input:    1, 1
Expected: 1

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution2 approaches

1. 1-D rolling row

Time O(m·n)Space O(n)

paths(r, c) = paths(r − 1, c) + paths(r, c − 1). One row suffices: row[c] += row[c − 1].

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];
}

2. Combinatorics

Time O(min(m, n))Space O(1)

Choose which m − 1 of the m + n − 2 moves go down: C(m + n − 2, m − 1).

function uniquePaths(m, n) {
let res = 1;
for (let i = 1; i < m; i++) res = (res * (n - 1 + i)) / i;
return Math.round(res);
}