Blind 75 - problem 21 : Unique Paths

 

Unique Paths – LeetCode Solution with Detailed Explanation

Problem Statement

A robot is located at the top-left corner of an m x n grid.

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.

How many possible unique paths exist for the robot to reach the destination?

Example 1:

Input:

m = 3, n = 7

Output:

28

Explanation:
There are 28 unique paths from (0,0) to (m-1, n-1).

---

Example 2:

Input:

m = 3, n = 2

Output:

3

Explanation:

• The possible unique paths are:
  1. Right → Down → Down
  2. Down → Right → Down
  3. Down → Down → Right

---

Optimal Approach – Dynamic Programming (DP)

Since the robot can only move right or down, we can use Dynamic Programming (DP) to efficiently count the number of paths.

Key Observations:

1. The robot starts at (0,0) and moves only right (→) or down (↓).
2. The destination is (m-1, n-1).
3. The number of unique paths to any cell (i, j) is the sum of paths from:
   • The top cell (i-1, j).
   • The left cell (i, j-1).

Dynamic Programming Formula:

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

• The base case is when i=0 or j=0, where only one way exists (moving straight).

---

LeetCode-Compatible C++ Code Implementation

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 of Code

1. Initialize a dp array with m x n dimensions, filled with 1.
   • The first row and first column are all 1 (since there’s only one way to move right/down).
2. Loop through the grid (i=1 to m-1 and j=1 to n-1):
   • Use the formula dp[i][j] = dp[i-1][j] + dp[i][j-1].
   • The result at dp[m-1][n-1] is the total unique paths.
3. Return dp[m-1][n-1] as the final answer.

---

Dry Run / Execution Steps

Input: m = 3, n = 3

DP Table Calculation:

i,j	(0,0)	(0,1)	(0,2)
(1,0)	1	1	1
(2,0)	1	2	3

Final DP Table:

1   1   1  
1   2   3  
1   3   6  

Output: 6

---

Alternative Approaches & Why Not?

1. Brute Force – Recursion

• Try all possible paths by moving right or down recursively.
• Time Complexity: O(2^(m+n)) (Exponential)
• Space Complexity: O(m+n) (Recursion depth)
• Why Not? Too slow for large values of m and n.

2. Memoization (Top-Down DP)

• Use recursion but store intermediate results in a map<int, int> dp.
• Time Complexity: O(m*n)
• Space Complexity: O(m*n)

3. Combinatorial Approach (Best Solution)

We can calculate Unique Paths using the Binomial Coefficient formula:

$$C(m+n-2, m-1) = \frac{(m+n-2)!}{(m-1)! (n-1)!}$$

• Time Complexity: O(min(m, n))
• Space Complexity: O(1)
• Why Best? Avoids extra memory and is the fastest approach.

---

Best Solution & Why It’s Best

Approach	Time Complexity	Space Complexity	Optimal?
Brute Force Recursion	O(2^(m+n))	O(m+n)	❌ No (Too slow)
Memoization (Top-Down DP)	O(m*n)	O(m*n)	✅ Yes
Bottom-Up DP	O(m*n)	O(m*n)	✅ Yes
Combinatorial	O(min(m, n))	O(1)	✅ Best

The Combinatorial Approach is the best since it runs in O(min(m, n)) time and O(1) space.

---

Combinatorial Solution (Best Approach)

class Solution {
public:
    int uniquePaths(int m, int n) {
        long long res = 1;
        int N = m + n - 2;
        int r = min(m - 1, n - 1);

        for (int i = 1; i <= r; i++) {
            res = res * (N - i + 1) / i;
        }

        return res;
    }
};

Explanation:

1. Use the formula: $$C(m+n-2, m-1) = \frac{(m+n-2)!}{(m-1)! (n-1)!}$$
2. Avoid Factorial Overflow
   • Instead of computing full factorials, calculate incrementally.
3. Final Result: res holds the number of unique paths.

---

Conclusion

• We used Dynamic Programming (DP) and Combinatorial Math to solve the problem efficiently.
• The best solution is the Combinatorial Approach (O(1) space, O(min(m, n)) time).
• Similar problems to practice:
  • Minimum Path Sum
  • Unique Paths II (with Obstacles)
  • Climbing Stairs

🚀 This approach is optimal and ensures efficient calculations!