Unique Paths
Problem statement
A robot sits in the top-left cell of an m by n grid (m rows, n columns) and must reach the bottom-right cell. It can only move right or down, one cell per move. Return how many different routes it can take.
Both m and n are at least 1. A 1 by 1 grid has exactly one route: stay put.
Examples
Example 1
Input: m = 3, n = 4
Output: 10
Explanation: Every route makes 2 down moves and 3 right moves in some order, and there are 10 ways to arrange them.
Example 2
Input: m = 1, n = 6
Output: 1
Explanation: A single row leaves only one choice: go right five times.
Hints
Approach
Combinatorics. Every route has exactly m - 1 down moves and n - 1 right moves, m + n - 2 moves in total, and a route is fixed by choosing which of those moves are downs. So the answer is C(m + n - 2, k) with k = min(m, n) - 1.
Compute it incrementally as result = result · (N - k + i) / i for i from 1 to k. Each intermediate value is itself a binomial coefficient, so every division is exact. Use a 64-bit integer in Java so the multiplication doesn't overflow before the division.
O(min(m, n))Space O(1)def unique_paths(m, n): total, k = m + n - 2, min(m, n) - 1 result = 1 for i in range(1, k + 1): result = result * (total - k + i) // i return result print(unique_paths(3, 4))print(unique_paths(1, 6))Follow-up questions
- Some cells are blocked (Unique Paths II).
- Each cell has a cost; return the cheapest route instead of the count (Minimum Path Sum).
Frequently asked questions
It is a standard grid DP, the 2-D version of Climbing Stairs, and it often opens the DP part of a loop. It also rewards spotting a closed-form answer, which interviewers like to see, and the one-row trick is a common space optimisation for many grid DPs.
After step i, result equals C(total - k + i, i), a whole number. Multiplying the previous whole number by the next factor and then dividing by i lands exactly on that coefficient, so no rounding happens as long as you multiply before dividing.
Use the DP, not the formula. A blocked cell has 0 routes, and every other cell is the sum of the cell above and the cell to the left (Unique Paths II). The one-row version still works: set row[c] = 0 on a blocked cell.