Unique Paths
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
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);}