Unique Paths Medium 0 attempts
LeetCode ↗

Unique Paths

Medium Dynamic ProgrammingMemoization LeetCode

Picture a robot sitting in the top-left cell of an m x n grid, able to step only one cell to the right or one cell down at a time. Work out how many distinct routes get it to the bottom-right cell.

Input Format
Implement uniquePaths(m, n). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 ยท Run Sample

Input
m = 3
n = 7
Output
28

Example 2

Input
m = 3
n = 2
Output
3
Constraints
  • 1 <= m, n <= 100
  • The answer is at most 2 * 10^9.
Test Cases (2)
Case 1
Args: [3,7] Expected: 28
Case 2
Args: [3,2] Expected: 3
Topics
Dynamic ProgrammingMemoization

DP

javascript
function uniquePaths(m, n) {
  const dp = Array(n).fill(1);
  for (let i = 1; i < m; i++)
    for (let j = 1; j < n; j++)
      dp[j] += dp[j-1];
  return dp[n-1];
}

Time: O(mn) | Space: O(n)

Saved in this browser only. Private to you.

JavaScript