63. Unique Paths II – Leetcode Solutions

June 20, 2024

Table of Contents

Description:

You are given an m x n integer array grid. There is a robot initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle.

Return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The testcases are generated so that the answer will be less than or equal to 2 * 10⁹.

Examples:

Example 1:

Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
Explanation: There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

Example 2:

Input: obstacleGrid = [[0,1],[0,0]]
Output: 1

Solution in Python:

To solve the problem of finding the number of unique paths for a robot to reach the bottom-right corner of a grid with obstacles, we can use a dynamic programming approach.

Steps to Solve the Problem:

Define the Problem in Terms of Subproblems:
- We need to calculate the number of ways to reach each cell (i, j) from the starting cell (0, 0) while avoiding obstacles.
- If a cell has an obstacle (1), the number of ways to reach that cell is 0.
- The robot can only move right or down, so the number of ways to reach cell (i, j) is the sum of the number of ways to reach cell (i-1, j) (from the cell above) and cell (i, j-1) (from the cell to the left), provided those cells are not obstacles.
Initialize the Base Cases:
- The starting cell (0, 0) can only be reached if it is not an obstacle.
- If any cell in the first row or first column is an obstacle, all cells beyond it in that row or column are unreachable.
Create and Populate the DP Table:
- Create a 2D array dp where dp[i][j] represents the number of unique paths to cell (i, j).
- Iterate through the grid, and for each cell (i, j), update dp[i][j] based on the values from the cell above it and the cell to the left of it, while considering obstacles.
Return the Result:
- The value at dp[m-1][n-1] will give us the number of unique paths to the bottom-right corner of the grid.

Python

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        # Get the dimensions of the grid
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        
        # If the starting or ending point is an obstacle, return 0
        if obstacleGrid[0][0] == 1 or obstacleGrid[m-1][n-1] == 1:
            return 0
        
        # Create a 2D dp array initialized to 0
        dp = [[0] * n for _ in range(m)]
        
        # Initialize the starting point
        dp[0][0] = 1
        
        # Fill the first row
        for j in range(1, n):
            dp[0][j] = dp[0][j-1] if obstacleGrid[0][j] == 0 else 0
        
        # Fill the first column
        for i in range(1, m):
            dp[i][0] = dp[i-1][0] if obstacleGrid[i][0] == 0 else 0
        
        # Fill the dp table
        for i in range(1, m):
            for j in range(1, n):
                if obstacleGrid[i][j] == 0:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
                else:
                    dp[i][j] = 0
        
        # Return the number of unique paths to reach the bottom-right corner
        return dp[m-1][n-1]

Detailed Explanation:

Initialization:
- m, n = len(obstacleGrid), len(obstacleGrid[0]) gets the dimensions of the grid.
- The condition if obstacleGrid[0][0] == 1 or obstacleGrid[m-1][n-1] == 1 checks if the start or end point is an obstacle and returns 0 if true.
- dp = [[0] * n for _ in range(m)] creates an m x n grid initialized to 0.
Setting Up the Starting Point:
- dp[0][0] = 1 initializes the starting point as reachable if it is not an obstacle.
Filling the First Row and Column:
- The loops for j in range(1, n): dp[0][j] = dp[0][j-1] if obstacleGrid[0][j] == 0 else 0 and for i in range(1, m): dp[i][0] = dp[i-1][0] if obstacleGrid[i][0] == 0 else 0 fill the first row and column while considering obstacles.
Filling the DP Table:
- The nested loop for i in range(1, m): for j in range(1, n): if obstacleGrid[i][j] == 0: dp[i][j] = dp[i-1][j] + dp[i][j-1] else: dp[i][j] = 0 computes the number of ways to reach each cell (i, j) by summing the ways to reach the cell from above (dp[i-1][j]) and from the left (dp[i][j-1]), while considering obstacles.
Result:
- return dp[m-1][n-1] returns the value at the bottom-right corner of the grid, which represents the number of unique paths to that cell.

This approach ensures that we efficiently compute the number of unique paths using dynamic programming while avoiding obstacles in O(m * n) time complexity, which is suitable given the problem constraints.

Solution in Javascript:

JavaScript

/**
 * @param {number[][]} obstacleGrid
 * @return {number}
 */
var uniquePathsWithObstacles = function(obstacleGrid) {
    // Get the dimensions of the grid
    const m = obstacleGrid.length;
    const n = obstacleGrid[0].length;
    
    // If the starting or ending point is an obstacle, return 0
    if (obstacleGrid[0][0] === 1 || obstacleGrid[m-1][n-1] === 1) {
        return 0;
    }
    
    // Create a 2D dp array initialized to 0
    const dp = Array.from({ length: m }, () => Array(n).fill(0));
    
    // Initialize the starting point
    dp[0][0] = 1;
    
    // Fill the first row
    for (let j = 1; j < n; j++) {
        dp[0][j] = obstacleGrid[0][j] === 0 ? dp[0][j-1] : 0;
    }
    
    // Fill the first column
    for (let i = 1; i < m; i++) {
        dp[i][0] = obstacleGrid[i][0] === 0 ? dp[i-1][0] : 0;
    }
    
    // Fill the dp table
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            if (obstacleGrid[i][j] === 0) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            } else {
                dp[i][j] = 0;
            }
        }
    }
    
    // Return the number of unique paths to reach the bottom-right corner
    return dp[m-1][n-1];
};

Solution in Java:

Java

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        // Get the dimensions of the grid
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        
        // If the starting or ending point is an obstacle, return 0
        if (obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1) {
            return 0;
        }
        
        // Create a 2D dp array initialized to 0
        int[][] dp = new int[m][n];
        
        // Initialize the starting point
        dp[0][0] = 1;
        
        // Fill the first row
        for (int j = 1; j < n; j++) {
            dp[0][j] = obstacleGrid[0][j] == 0 ? dp[0][j-1] : 0;
        }
        
        // Fill the first column
        for (int i = 1; i < m; i++) {
            dp[i][0] = obstacleGrid[i][0] == 0 ? dp[i-1][0] : 0;
        }
        
        // Fill the dp table
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 0) {
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                } else {
                    dp[i][j] = 0;
                }
            }
        }
        
        // Return the number of unique paths to reach the bottom-right corner
        return dp[m-1][n-1];
    }
}

Solution in C#:

C#

public class Solution {
    public int UniquePathsWithObstacles(int[][] obstacleGrid) {
        // Get the dimensions of the grid
        int m = obstacleGrid.Length;
        int n = obstacleGrid[0].Length;

        // If the starting or ending point is an obstacle, return 0
        if (obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1) {
            return 0;
        }

        // Create a 2D dp array initialized to 0
        int[][] dp = new int[m][];
        for (int i = 0; i < m; i++) {
            dp[i] = new int[n];
        }

        // Initialize the starting point
        dp[0][0] = 1;

        // Fill the first row
        for (int j = 1; j < n; j++) {
            dp[0][j] = obstacleGrid[0][j] == 0 ? dp[0][j-1] : 0;
        }

        // Fill the first column
        for (int i = 1; i < m; i++) {
            dp[i][0] = obstacleGrid[i][0] == 0 ? dp[i-1][0] : 0;
        }

        // Fill the dp table
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 0) {
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                } else {
                    dp[i][j] = 0;
                }
            }
        }

        // Return the number of unique paths to reach the bottom-right corner
        return dp[m-1][n-1];
    }
}

63. Unique Paths II – Leetcode Solutions

Description:

Solution in Python:

Solution in Javascript:

Solution in Java:

Solution in C#:

Popular

21. Merge Two Sorted Lists – Leetcode Solutions

282. Expression Add Operators – Leetcode Solutions

332. Reconstruct Itinerary – Leetcode Solutions

PEP 8: The Python Style Guide – Basics

111. Minimum Depth of Binary Tree – Leetcode Solutions

228. Summary Ranges – Leetcode Solutions

Working with Python Modules: Creating, Importing, and Using Them Effectively

63. Unique Paths II – Leetcode Solutions

Description:

Solution in Python:

Solution in Javascript:

Solution in Java:

Solution in C#:

Related Post

Popular