Problem
You are given anm x n grid. A robot starts at the top-left corner and needs to reach the bottom-right corner. The robot can move only right or down.
Return the number of unique paths from the starting cell to the destination.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
m = 3
n = 3
[S] → [ ] → [ ]
↓ ↓ ↓
[ ] → [ ] → [ ]
↓ ↓ ↓
[ ] → [ ] → [E]
Output
6Solution
This problem can be solved using Memoization.The robot starts at the top-left corner
(0, 0). From every cell, it has two choices: move down or move right.
From the starting position, we calculate the paths after taking the first move in both possible directions:
Move Right → paths(0, 1)
Move Down → paths(1, 0)paths(i, j) = paths(i + 1, j) + paths(i, j + 1)0. If the robot reaches the bottom-right corner, it has found one valid path, so we return 1.
The same cell can be reached through multiple paths, so we store its result in a memoization array and reuse it when needed.
class Solution {
public int uniquePaths(int m, int n) {
Integer[][] memo = new Integer[m][n];
return uniquePathsHelper(m, n, 0, 0, memo);
}
private int uniquePathsHelper(int m, int n, int i, int j, Integer[][] memo) {
// Destination reached
if (i == m - 1 && j == n - 1)
return 1;
// Invalid path
if (i == m || j == n)
return 0;
// Return already calculated result
if (memo[i][j] != null)
return memo[i][j];
// Possible moves: down or right
return memo[i][j] = uniquePathsHelper(m, n, i + 1, j, memo)
+ uniquePathsHelper(m, n, i, j + 1, memo);
}
}
Complexity
Each cell is calculated only once, resulting inO(m × n) time complexity. The memoization array requires O(m × n) space, and the recursion stack can grow up to O(m + n).
Tabulation Approach
Instead of recursively calculating the number of paths from each cell, we can build the solution using a DP table.The first row and first column contain only 1 path to every cell because the robot can move only right or down.
For every other cell, the robot can arrive either from the top or from the left. Therefore:
dp[row][col] = dp[row - 1][col] + dp[row][col - 1]
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
// One path to every cell in the first row and column.
for (int i = 0; i < m; i++) {
dp[i][0] = 1;
}
for (int j = 0; j < n; j++) {
dp[0][j] = 1;
}
// Build the remaining cells.
for (int row = 1; row < m; row++) {
for (int col = 1; col < n; col++) {
dp[row][col] = dp[row - 1][col]
+ dp[row][col - 1];
}
}
return dp[m - 1][n - 1];
}
}
Complexity
Each cell is calculated once, resulting inO(m × n) time complexity. The DP table stores m × n values, requiring O(m × n) space.
Space Optimized Approach
In the tabulation approach, each cell depends only on the value above it and the value to its left. Therefore, we do not need to store the entire grid.We can use a one-dimensional array where
dp[col] represents the number of paths to the current cell. As we move row by row, dp[col] already contains the value from the cell above, while dp[col - 1] contains the value from the left.
class Solution {
public int uniquePaths(int m, int n) {
int[] dp = new int[n];
Arrays.fill(dp, 1);
for (int row = 1; row < m; row++) {
for (int col = 1; col < n; col++) {
// Paths from above + paths from the left.
dp[col] = dp[col] + dp[col - 1];
}
}
return dp[n - 1];
}
}
Complexity
Each cell is processed once, resulting inO(m × n) time complexity. The one-dimensional DP array requires O(n) space.