LeetCode Solution 62 - Unique Paths

Problem Statement

A robot is located at the top-left corner of an m x n grid (marked 'Start'). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish').

How many unique paths are there from the start to the finish?

Constraints:

• 1 <= m, n <= 100
• The grid contains only open spaces (no obstacles).

Optimal Approach - Dynamic Programming (Bottom-Up)

The most efficient way to solve this problem is Dynamic Programming (DP).

Explanation:

1. Define dp[i][j] as the number of unique paths to cell (i, j).

2. The robot can move only right or down, so the recurrence relation is:

   $dp[i][j] = dp[i-1][j] + dp[i][j-1]$

3. Base Cases:

   • The first row can only be reached from the left (dp[0][j] = 1).
   • The first column can only be reached from above (dp[i][0] = 1).

C++ Code (LeetCode-Compatible)

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n, 1));
        
        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];
    }
};

Step-by-Step Explanation

1. Initialize a dp matrix of size m x n with 1s (since there's only one way to reach any cell in the first row or first column).
2. Iterate through the grid, starting from (1,1), updating dp[i][j] using dp[i-1][j] + dp[i][j-1].
3. Return dp[m-1][n-1], which contains the total unique paths.

Dry Run / Execution Steps

Example:

Input: m = 3, n = 3

DP Table Updates:

i\j	0	1	2
0	1	1	1
1	1	2	3
2	1	3	6

Output: 6

Alternative Approaches & Why Not?

Approach	Time Complexity	Space Complexity	Why Not?
Brute Force (Recursion)	Exponential $O(2^{(m+n)})$	O(m+n)	Too slow for large inputs
Memoization (Top-Down DP)	O(m * n)	O(m * n)	Extra space usage
Bottom-Up DP (Best)	O(m * n)	O(m * n)	Efficient and avoids recursion overhead
Combinatorial (Optimal)	O(min(m, n))	O(1)	Uses mathematical formula $C(m+n-2, m-1)$

Best Solution & Why It’s Best

The Combinatorial Approach is the most optimized because:

1. It reduces time complexity to O(min(m, n)).
2. It avoids unnecessary O(m*n) space usage.
3. It directly computes the result using: $C(m+n-2, m-1) = \frac{(m+n-2)!}{(m-1)! (n-1)!}$

C++ Code (Combinatorial Solution)

class Solution {
public:
    int uniquePaths(int m, int n) {
        long long res = 1;
        for (int i = 1; i <= min(m-1, n-1); i++) {
            res = res * (m + n - 1 - i) / i;
        }
        return res;
    }
};

Complexity Analysis

• Time Complexity:
  • DP: O(m * n)
  • Combinatorial: O(min(m, n))
• Space Complexity:
  • DP: O(m * n)
  • Combinatorial: O(1)

Conclusion

• The best approach is Combinatorial Mathematics.
• Dynamic Programming is still a good approach for understanding and breaking down the problem.
• Recommended practice problems:
  • Minimum Path Sum (LeetCode 64)
  • Unique Paths II (LeetCode 63)
  • Climbing Stairs (LeetCode 70)