Language Selection
Choose your preferred programming language
Showing: Python
Problem Statement
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.
Input:
- Two integers m and n representing the dimensions of the grid
Output:
- Number of unique paths from top-left to bottom-right
Constraints:
- 1 ≤ m, n ≤ 100
Examples:
Example 1:
Input: m = 3, n = 7
Output: 28
Explanation: There are 28 unique paths from (0,0) to (2,6)
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
Example 3:
Input: m = 1, n = 1
Output: 1
Explanation: Only one cell, so only one path
Solutions
Approach 1: 2D Dynamic Programming
Algorithm:
- Create 2D DP table where dp[i][j] = number of paths to reach cell (i,j)
- Base cases: dp[0][j] = 1 (only one way to reach first row), dp[i][0] = 1 (only one way to reach first column)
- For other cells: dp[i][j] = dp[i-1][j] + dp[i][j-1]
Python:
def uniquePaths_2d(m, n):
"""
2D DP solution for unique paths
Time: O(m * n) - fill entire grid
Space: O(m * n) - DP table
"""
# dp[i][j] = number of unique paths to reach cell (i, j)
dp = [[0] * n for _ in range(m)]
# Base cases: first row and first column
# Only one way to reach any cell in first row (keep going right)
for j in range(n):
dp[0][j] = 1
# Only one way to reach any cell in first column (keep going down)
for i in range(m):
dp[i][0] = 1
# Fill the rest of the table
for i in range(1, m):
for j in range(1, n):
# Can reach (i,j) from (i-1,j) or (i,j-1)
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
def uniquePaths_2d_clean(m, n):
"""
Clean 2D DP implementation
Time: O(m * n)
Space: O(m * n)
"""
dp = [[1] * n for _ in range(m)]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
# Example usage
print(uniquePaths_2d(3, 7)) # Output: 28
Java:
class Solution {
/**
* 2D DP solution for unique paths
* Time: O(m * n)
* Space: O(m * n)
*/
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
// Base cases: first row and first column
for (int j = 0; j < n; j++) {
dp[0][j] = 1;
}
for (int i = 0; i < m; i++) {
dp[i][0] = 1;
}
// Fill the rest of the table
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m-1][n-1];
}
/**
* Clean 2D DP implementation
* Time: O(m * n)
* Space: O(m * n)
*/
public int uniquePathsClean(int m, int n) {
int[][] dp = new int[m][n];
// Initialize with 1s
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
dp[i][j] = 1;
}
}
// Fill DP table
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m-1][n-1];
}
}
Go:
// uniquePaths - 2D DP solution
// Time: O(m * n)
// Space: O(m * n)
func uniquePaths(m int, n int) int {
dp := make([][]int, m)
for i := range dp {
dp[i] = make([]int, n)
}
// Base cases
for j := 0; j < n; j++ {
dp[0][j] = 1
}
for i := 0; i < m; i++ {
dp[i][0] = 1
}
// Fill DP table
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
dp[i][j] = dp[i-1][j] + dp[i][j-1]
}
}
return dp[m-1][n-1]
}
JavaScript:
/**
* 2D DP solution for unique paths
* Time: O(m * n)
* Space: O(m * n)
*/
function uniquePaths(m, n) {
const dp = Array(m).fill().map(() => Array(n).fill(0));
// Base cases
for (let j = 0; j < n; j++) {
dp[0][j] = 1;
}
for (let i = 0; i < m; i++) {
dp[i][0] = 1;
}
// Fill DP table
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m-1][n-1];
}
C#:
public class Solution {
/// <summary>
/// 2D DP solution for unique paths
/// Time: O(m * n)
/// Space: O(m * n)
/// </summary>
public int UniquePaths(int m, int n) {
int[,] dp = new int[m, n];
// Base cases
for (int j = 0; j < n; j++) {
dp[0, j] = 1;
}
for (int i = 0; i < m; i++) {
dp[i, 0] = 1;
}
// Fill DP table
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i, j] = dp[i-1, j] + dp[i, j-1];
}
}
return dp[m-1, n-1];
}
}
Approach 2: Space Optimized DP (1D)
Since we only need the previous row, optimize space to O(n).
Python:
def uniquePaths_optimized(m, n):
"""
Space-optimized DP solution
Time: O(m * n) - still process all cells
Space: O(n) - only store one row
"""
# dp[j] = number of paths to reach current row, column j
dp = [1] * n # First row is all 1s
# Process each row starting from row 1
for i in range(1, m):
for j in range(1, n):
# dp[j] currently holds paths from previous row (above)
# dp[j-1] holds paths from current row (left)
dp[j] += dp[j-1]
return dp[n-1]
def uniquePaths_optimized_verbose(m, n):
"""
Verbose space-optimized version
Time: O(m * n)
Space: O(n)
"""
dp = [1] * n
print(f"Initial row: {dp}")
for i in range(1, m):
print(f"Processing row {i}:")
for j in range(1, n):
old_value = dp[j]
dp[j] += dp[j-1]
print(f" dp[{j}]: {old_value} + {dp[j-1]} = {dp[j]}")
print(f" Row {i} complete: {dp}")
return dp[n-1]
# Example usage
print(uniquePaths_optimized(3, 7)) # Output: 28
Java:
class Solution {
/**
* Space-optimized DP solution
* Time: O(m * n)
* Space: O(n)
*/
public int uniquePaths(int m, int n) {
int[] dp = new int[n];
// Initialize first row
for (int j = 0; j < n; j++) {
dp[j] = 1;
}
// Process each row starting from row 1
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[j] += dp[j-1];
}
}
return dp[n-1];
}
/**
* Even more optimized - use smaller dimension
* Time: O(m * n)
* Space: O(min(m, n))
*/
public int uniquePathsOptimal(int m, int n) {
if (m > n) {
return uniquePathsOptimal(n, m); // Ensure n is larger
}
int[] dp = new int[m];
Arrays.fill(dp, 1);
for (int j = 1; j < n; j++) {
for (int i = 1; i < m; i++) {
dp[i] += dp[i-1];
}
}
return dp[m-1];
}
}
Approach 3: Mathematical Solution (Combinatorics)
The problem is equivalent to choosing positions for right moves among total moves.
Python:
def uniquePaths_math(m, n):
"""
Mathematical solution using combinatorics
Time: O(min(m, n)) - for computing combination
Space: O(1) - constant space
"""
# Total moves needed: (m-1) down + (n-1) right = m+n-2
# Need to choose (m-1) positions for down moves
# This is C(m+n-2, m-1) = C(m+n-2, n-1)
total_moves = m + n - 2
down_moves = m - 1
# Calculate C(total_moves, down_moves) efficiently
if down_moves > total_moves - down_moves:
down_moves = total_moves - down_moves # Use smaller number
result = 1
for i in range(down_moves):
result = result * (total_moves - i) // (i + 1)
return result
def uniquePaths_math_alternative(m, n):
"""
Alternative mathematical calculation
Time: O(min(m, n))
Space: O(1)
"""
from math import comb
return comb(m + n - 2, m - 1)
# Example usage
print(uniquePaths_math(3, 7)) # Output: 28
Key Insights
- Grid DP Pattern: Each cell value depends on cell above and cell to the left
- Base Cases: First row and column have only one path (straight line)
- Recurrence: paths[i][j] = paths[i-1][j] + paths[i][j-1]
- Space Optimization: Only need previous row, can use 1D array
- Mathematical Connection: This is a combinatorics problem - choosing positions for moves
Edge Cases
- Single cell: m=1, n=1 should return 1
- Single row: m=1, any n should return 1
- Single column: any m, n=1 should return 1
- Small grids: 2x2, 2x3 grids for verification
Test Cases
def test_unique_paths():
test_cases = [
(3, 7, 28),
(3, 2, 3),
(1, 1, 1),
(1, 10, 1),
(10, 1, 1),
(2, 2, 2),
(3, 3, 6)
]
for m, n, expected in test_cases:
result_dp = uniquePaths_optimized(m, n)
result_math = uniquePaths_math(m, n)
assert result_dp == expected, f"DP: m={m}, n={n}, expected={expected}, got={result_dp}"
assert result_math == expected, f"Math: m={m}, n={n}, expected={expected}, got={result_math}"
print(f"uniquePaths({m}, {n}) = {result_dp} ✓")
test_unique_paths()
Common Mistakes
- Off-by-one errors: Confusion between grid size and number of moves
- Base case handling: Not properly initializing first row and column
- Index confusion: Using wrong indices in recurrence relation
- Space optimization: Overwriting values that are still needed
- Mathematical formula: Incorrect combination calculation
Follow-up Questions
- Unique Paths II: Grid with obstacles that block certain cells
- Minimum path sum: Find path with minimum sum instead of counting paths
- Path reconstruction: Return actual paths, not just count
- 3D version: Extend to 3D grid with up/down movements
- Circular grid: Grid that wraps around edges
- Variable step sizes: Allow larger steps in one direction
Interview Tips
- Start with examples: Draw small grids and count paths manually
- Identify pattern: Show how each cell depends on neighbors
- Discuss approaches: Compare DP vs mathematical solutions
- Space optimization: Show progression from 2D to 1D
- Handle edge cases: Test with small grids and edge dimensions
- Mathematical insight: Explain the combinatorics connection
- Time complexity: Discuss why DP and math have different complexities