Solving Unique Paths II (LeetCode #63)

Introduction:

Today, we’ll solve Unique Paths II (LeetCode #63), which is a variation of the original Unique Paths problem. This time, the grid has obstacles that block certain paths, and our goal is to calculate the number of unique paths the robot can take from the top-left corner to the bottom-right corner. We’ll use Dynamic Programming (DP) to efficiently solve this problem.

If you’re interested in a video walkthrough of this solution, check out my explanation on YouTube here.

---

Problem Overview:

You’re given an m x n grid where:

• 0 represents an open space,
• 1 represents an obstacle that the robot cannot pass through.

The robot can only move right or down at any point. The task is to return the number of unique paths the robot can take to reach the bottom-right corner from the top-left corner, avoiding obstacles.

Example:

Input:

luaCopy codeobstacleGrid = [[0,0,0],
                [0,1,0],
                [0,0,0]]

Output: 2

Explanation: The robot can take the following paths:

1. Right → Right → Down → Down
2. Down → Down → Right → Right

---

Solution Approach:

We’ll use Dynamic Programming (DP) to solve the problem in an optimal manner.

1. Grid Representation: We’ll represent the number of ways to reach a particular cell in the grid using a DP array. Initially, there is only one way to reach the starting point.
2. Obstacle Handling: If a cell contains an obstacle (1), we set its value in the DP array to 0, indicating that there are no valid paths through that cell.
3. Update the DP Array: For each cell, if there’s no obstacle, we calculate the number of paths to that cell by summing the values of the cell directly above it and the one to the left.

---

Code Implementation:

javaCopy codeclass Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int n = obstacleGrid[0].length;
        int[] dp = new int[n];
        dp[0] = 1;

        for (int[] row : obstacleGrid) {
            for (int j = 0; j < n; j++) {
                if (row[j] == 1) {
                    dp[j] = 0;  // No paths through an obstacle
                } else if (j > 0) {
                    dp[j] += dp[j - 1];  // Sum paths from top and left
                }
            }
        }

        return dp[n - 1];  // The bottom-right corner has the result
    }
}

---

Explanation of the Code:

1. Initial Setup: We create a DP array dp[] where dp[j] stores the number of ways to reach column j in the current row. Initially, dp[0] = 1, meaning there is one way to start at the top-left corner.
2. Dynamic Programming Logic:
   • For each row in the obstacle grid, we iterate through each cell:
     • If the cell is an obstacle (1), we set dp[j] = 0 because the robot cannot pass through it.
     • If there’s no obstacle and we’re not in the first column (j > 0), we update dp[j] by adding the value from the cell directly to its left (dp[j - 1]).
3. Result: At the end of the iterations, dp[n-1] contains the number of unique paths to the bottom-right corner.

---

Explanation with Example:

Let’s walk through the input:

javaCopy codeobstacleGrid = [[0,0,0],
                [0,1,0],
                [0,0,0]]

1. We initialize our DP array: dp = [1, 0, 0].
2. First Row (no obstacles):
   • After processing, dp = [1, 1, 1], meaning there’s 1 way to reach each cell in the first row.
3. Second Row (one obstacle at grid[1][1]):
   • After processing, dp = [1, 0, 1]. The obstacle blocks paths to the second cell, so we skip it, but the rightmost cell can still be reached from the left.
4. Third Row (no obstacles):
   • After processing, dp = [1, 1, 2]. The rightmost cell can be reached either from above or from the left, resulting in 2 unique paths.

Thus, the result is 2.

---

Conclusion:

The dynamic programming approach ensures that we efficiently compute the number of unique paths, even with obstacles in the grid. The time complexity is O(m * n), making it very efficient for large grids.

Dynamic Programming is a powerful technique for solving pathfinding problems like this one. For a step-by-step walkthrough, check out my detailed explanation in the YouTube video here.

Feel free to ask questions or leave feedback in the comments. Happy coding!