Unique Paths

The key idea

Every cell can only be reached from the cell directly above it or the cell directly to its left, so the number of paths to a cell is the sum of the paths to those two neighbors. The whole top row and left column have exactly one path each.

Problem

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e. grid[0][0]). The robot tries to move to the bottom-right corner (i.e. grid[m-1][n-1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 10^9.

Constraints

1 <= m, n <= 100
The answer is guaranteed to be less than or equal to 2 * 10^9.

Examples

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

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

Complexity

Time: O(m*n) Space: O(n)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →