LeetCode Solution 62 - Unique Paths

Problem Statement

You are given an m x n grid. You are a robot starting at the top-left corner (0,0), and your goal is to reach the bottom-right corner (m-1, n-1). You can only move down or right at any step.

Return the total number of unique paths to reach the destination.

Constraints:

• 1 <= m, n <= 100
• The input grid has no obstacles.

---

Optimal Approach - Dynamic Programming (DP)

The most efficient way to solve this problem is by using Dynamic Programming (DP). We use a dp table where dp[i][j] represents the number of ways to reach cell (i, j).

Recurrence Relation:

• If we are at dp[i][j], we could have come from dp[i-1][j] (top) or dp[i][j-1] (left).
• So, the formula is:
  dp[i][j] = dp[i-1][j] + dp[i][j-1]
• Base Case: dp[0][j] = 1 (only one way to move right) and dp[i][0] = 1 (only one way to move down).

---

C++ Code Implementation (LeetCode-Submittable)

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 DP Table: Create a 2D table dp[m][n], where each cell represents the number of paths to reach that position.
2. Set Base Cases: The first row and first column are initialized with 1 because there is only one way to move either right (first row) or down (first column).
3. Iterate Through Grid: Use a nested loop to fill each cell using the formula dp[i][j] = dp[i-1][j] + dp[i][j-1].
4. Return Final Answer: The answer is stored in dp[m-1][n-1] (bottom-right corner).

---

Dry Run / Execution Example

Input: m = 3, n = 3

DP Table Progression:

1  1  1
1  2  3
1  3  6

Output: 6

Explanation: There are 6 unique paths from (0,0) to (2,2).

---

Alternative Approaches & Why Not?

Approach	Time Complexity	Space Complexity	Why Not Optimal?
Recursion	O(2^(m+n))	O(m+n) (stack)	Exponential time, very slow
DP (2D Table)	O(m*n)	O(m*n)	Uses extra memory
DP (1D Array)	O(m*n)	O(n)	Best balance of speed & memory
Combinatorics	O(1)	O(1)	Fastest but harder to understand

---

Best Solution - Optimized DP (1D Array)

Since we only need values from the previous row, we can optimize DP to use a single 1D array.

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<int> dp(n, 1);
        
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[j] += dp[j - 1];
            }
        }
        return dp[n - 1];
    }
};

Why is this best?

• Time Complexity: O(m*n) (same as 2D DP)
• Space Complexity: O(n) (better than O(m*n), saves memory)

---

Complexity Analysis

Approach	Time Complexity	Space Complexity
Brute Force Recursion	O(2^(m+n))	O(m+n)
2D DP Table	O(m*n)	O(m*n)
1D DP (Optimized)	O(m*n)	O(n)
Combinatorial Solution	O(1)	O(1)

---

Conclusion

• Best Approach: Optimized 1D DP (O(m*n), O(n)).
• Alternative Approach: Combinatorics for a quick mathematical solution (O(1)).
• Practice Similar Problems:
  • Minimum Path Sum
  • Robot Grid with Obstacles
  • Unique Paths II

Want to master DP? Keep practicing similar problems and explore more optimized solutions!