LeetCode Solution 63 - Unique Paths II

Problem Statement

Given an m x n grid filled with obstacles, determine the number of unique paths from the top-left corner (0,0) to the bottom-right corner (m-1, n-1). You can only move either down or right at any point in time.

Constraints:

• 1 <= m, n <= 100
• grid[i][j] is either 0 (empty space) or 1 (obstacle).
• The starting and ending cells are always 0.

Optimal Approach - Dynamic Programming

Idea:

We use a Dynamic Programming (DP) approach where:

• dp[i][j] represents the number of ways to reach cell (i, j).
• If grid[i][j] == 1, then dp[i][j] = 0 (no path through an obstacle).
• Otherwise, we sum the number of paths from the top (dp[i-1][j]) and left (dp[i][j-1]).
• Base case: dp[0][0] = 1 if it's not an obstacle.

C++ Solution - LeetCode Submittable

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        if (obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1) return 0;
        
        vector<vector<int>> dp(m, vector<int>(n, 0));
        dp[0][0] = 1;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    dp[i][j] = 0; // Blocked cell
                } else {
                    if (i > 0) dp[i][j] += dp[i-1][j];
                    if (j > 0) dp[i][j] += dp[i][j-1];
                }
            }
        }
        
        return dp[m-1][n-1];
    }
};

Step-by-Step Explanation:

1. Base Case Handling: If grid[0][0] or grid[m-1][n-1] is 1, return 0 immediately.
2. Initialize DP Table: Create a 2D DP array dp[m][n].
3. DP Transition:
   • If grid[i][j] == 1, set dp[i][j] = 0 (no path through obstacles).
   • Else, set dp[i][j] = dp[i-1][j] + dp[i][j-1].
4. Final Answer: Return dp[m-1][n-1], which contains the total unique paths.

Dry Run Example:

Input:

[ [0,0,0],
  [0,1,0],
  [0,0,0] ]

Execution:

dp = [ [1, 1, 1],
       [1, 0, 1],
       [1, 1, 2] ]

Output:

2 unique paths.

Alternative Approaches:

Approach	Time Complexity	Space Complexity	Reason for Rejection
Recursion	Exponential	O(1)	Too slow
Memoization	O(m*n)	O(m*n)	Requires recursion stack
DP (Optimal)	O(m*n)	O(m*n)	Best solution
DP with O(n) Space	O(m*n)	O(n)	Optimized space

Complexity Analysis:

• Time Complexity: O(m*n), since we iterate through each cell once.
• Space Complexity: O(m*n) due to DP table (can be reduced to O(n)).

Conclusion:

• The DP solution is the most optimal, balancing speed and memory.
• Similar problems:
  • Unique Paths I
  • Minimum Path Sum

This structured guide ensures a well-documented, efficient, and LeetCode-submittable solution for Unique Paths II.