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 * 109.
Example 1:
Input: m = 3, n = 7
Output: 28
Example 2:
Input: m = 3, n = 2
Output: 3
Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down
Constraints:
1 <= m, n <= 100
Approaches
4 approaches with complexity analysis and trade-offs.
This approach directly translates the problem's definition into a recursive function. The number of paths to a cell (r, c) is the sum of paths from the cell below (r+1, c) and the cell to the right (r, c+1). The recursion starts from (0, 0) and has a base case when it reaches the destination (m-1, n-1).
Algorithm
1. Define a recursive function countPaths(r, c)that returns the number of paths from cell(r, c) to the destination.
2. **Base Case 1:** If the robot goes out of bounds (r >= morc >= n), it's an invalid path. Return 0.
3. **Base Case 2:** If the robot reaches the destination (r == m - 1andc == n - 1), it has found one valid path. Return 1.
14. **Recursive Step:** For any other cell, the number of paths is the sum of paths from moving down and paths from moving right. Return
countPaths(r + 1, c) + countPaths(r, c + 1).
5. The initial call is countPaths(0, 0).
Walkthrough
We define a recursive function, say countPaths(r, c), which calculates the number of unique paths from the cell (r, c) to the destination (m-1, n-1). The function works as follows:
Base Cases:
If the robot reaches the destination (r == m-1 and c == n-1), it has found one valid path. So, we return 1.
If the robot goes out of the grid boundaries (r >= m or c >= n), it's an invalid path. So, we return 0.
Recursive Step:
For any other cell (r, c), the robot can either move down to (r+1, c) or right to (r, c+1).
The total number of paths from (r, c) is the sum of paths from these two subsequent cells: countPaths(r+1, c) + countPaths(r, c+1).
The initial call to the function will be countPaths(0, 0). This method suffers from a major drawback: it recomputes the number of paths for the same cells multiple times, leading to an exponential number of calls.
1public class Solution {2 public int uniquePaths(int m, int n) {3 return countPaths(0, 0, m, n);4 }56 private int countPaths(int r, int c, int m, int n) {7 // Base case: out of bounds8 if (r >= m || c >= n) {9 return 0;10 }11 // Base case: reached destination12 if (r == m - 1 && c == n - 1) {13 return 1;14 }15 // Recursive step16 return countPaths(r + 1, c, m, n) + countPaths(r, c + 1, m, n);17 }18}
Complexity
Time
O(2^(m+n))
Space
O(m + n)
Trade-offs
Pros
Simple to understand and implement.
Directly models the problem statement.
Cons
Extremely inefficient due to a massive number of redundant calculations (overlapping subproblems).
Will result in a 'Time Limit Exceeded' error for all but the smallest grid sizes.
Solutions
Solution
1class Solution {2public3 int uniquePaths(int m, int n) {4 int[] f = new int[n];5 Arrays.fill(f, 1);6 for (int i = 1; i < m; ++i) {7 for (int j = 1; j < n; ++j) {8 f[j] += f[j - 1];9 }10 }11 return f[n - 1];12 }13}
Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.
