[Dynamic Programming] Unique Paths II (Grid with Obstacles) - Medium

In dynamic programming, we have a problem called Unique Paths II. This problem is about finding how many unique paths we can take from the top-left to the bottom-right corner of a grid. The grid may have obstacles in some cells. Each cell can be empty, marked as (0), or it can have an obstacle, marked as (1). Our goal is to find a way to go around the obstacles to reach the end. We need to think carefully about the possible moves and use dynamic programming to find the number of paths quickly.

In this article, we will look at different ways to solve the Unique Paths II problem. First, we will understand the problem itself. Then, we will explore dynamic programming and recursive approaches with memoization. We will also show you how to use iterative dynamic programming in Java, Python, and C++. We will discuss how to make space use better and compare different methods. Lastly, we will answer some common questions about Unique Paths II.

  • [Dynamic Programming] Unique Paths II (Grid with Obstacles) - Medium Solution Strategies
  • Understanding the Problem Statement of Unique Paths II
  • Dynamic Programming Approach for Unique Paths II
  • Recursive Approach with Memoization for Unique Paths II
  • Iterative Dynamic Programming Solution in Java for Unique Paths II
  • Iterative Dynamic Programming Solution in Python for Unique Paths II
  • Iterative Dynamic Programming Solution in C++ for Unique Paths II
  • Optimizing Space Complexity for Unique Paths II
  • Comparative Analysis of Different Approaches for Unique Paths II
  • Frequently Asked Questions

Understanding the Problem Statement of Unique Paths II

The “Unique Paths II” problem is about finding how many unique paths we can take from the top-left corner to the bottom-right corner of a grid while avoiding obstacles. The grid is shown as a 2D array where:

  • 0 means an empty cell
  • 1 means an obstacle.

Our goal is to count all paths from the start position (0, 0) to the end position (m-1, n-1). Here, m is the number of rows and n is the number of columns in the grid.

Key Points:

  • We can only move down or right.
  • If the starting cell or the ending cell has an obstacle, then the number of unique paths is 0.
  • We must carefully handle obstacles so we can count paths correctly.

Example:

Let’s look at this grid:

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

The unique paths from (0, 0) to (2, 2) are:

  • Down → Down → Right → Right
  • Right → Down → Down → Right
  • Right → Right → Down → Down

In this case, we have 2 unique paths that avoid the obstacle at (1, 1).

To solve this problem well, we often use a dynamic programming approach. We create a table to track how many ways we can reach each cell in the grid while considering obstacles.

This problem is a type of the Unique Paths problem. We can learn more about it in related articles on dynamic programming like Dynamic Programming: Unique Paths in a Grid - Easy.

Dynamic Programming Approach for Unique Paths II

The Unique Paths II problem is about finding how many unique ways we can go from the top-left corner to the bottom-right corner of a grid. We need to avoid obstacles on the way. The grid is a 2D array. Here, 1 means there is an obstacle and 0 means the cell is free.

Dynamic Programming Table Initialization

To solve this with dynamic programming, we make a 2D array called dp. In this array, dp[i][j] shows how many unique paths lead to the cell (i, j). Here are the main steps:

  1. If the starting cell dp[0][0] has an obstacle, we return 0.
  2. If it is free, we set dp[0][0] = 1.
  3. For each cell in the grid, if it is not an obstacle, we find the number of paths by adding the paths from the top and left cells.

Dynamic Programming Transition Formula

We can write the transition formula like this: - If grid[i][j] is 0, then: dp[i][j] = dp[i-1][j] + dp[i][j-1] - If grid[i][j] is 1, then: dp[i][j] = 0

Java Implementation

public int uniquePathsWithObstacles(int[][] grid) {
    int m = grid.length;
    int n = grid[0].length;
    
    if (grid[0][0] == 1 || grid[m-1][n-1] == 1) return 0;

    int[][] dp = new int[m][n];
    dp[0][0] = 1;

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1) {
                dp[i][j] = 0;
            } 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];
}

Python Implementation

def uniquePathsWithObstacles(grid):
    m, n = len(grid), len(grid[0])
    
    if grid[0][0] == 1 or grid[m-1][n-1] == 1:
        return 0

    dp = [[0] * n for _ in range(m)]
    dp[0][0] = 1

    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1:
                dp[i][j] = 0
            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]

C++ Implementation

int uniquePathsWithObstacles(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    
    if (grid[0][0] == 1 || grid[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 (grid[i][j] == 1) {
                dp[i][j] = 0;
            } 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];
}

This dynamic programming way helps us find the number of unique paths around obstacles in the grid. We use results we found before to build the solution step by step. For more reading on similar problems, check Dynamic Programming: Unique Paths in a Grid.

Recursive Approach with Memoization for Unique Paths II

We can use a recursive method with memoization to solve the Unique Paths II problem. This method helps us break the problem into smaller parts. We save the results to avoid doing the same work again. This is really helpful when we have to move through a grid with obstacles.

Problem Definition

We have a 2D grid. Each cell can be 0 or 1. A cell with 0 is empty and a cell with 1 is an obstacle. Our job is to find how many unique paths there are from the top-left corner to the bottom-right corner. We can only move down or to the right.

Recursive Function

The recursive function checks all possible paths from the current cell to the destination. It also looks for obstacles. If a cell is out of bounds or has an obstacle, it gives back 0. If we reach the destination, it gives back 1.

def uniquePathsWithObstacles(grid):
    if not grid or grid[0][0] == 1 or grid[-1][-1] == 1:
        return 0

    rows, cols = len(grid), len(grid[0])
    memo = {}

    def dfs(x, y):
        if (x, y) in memo:
            return memo[(x, y)]
        if x >= rows or y >= cols or grid[x][y] == 1:
            return 0
        if x == rows - 1 and y == cols - 1:
            return 1

        memo[(x, y)] = dfs(x + 1, y) + dfs(x, y + 1)
        return memo[(x, y)]

    return dfs(0, 0)

Function Explanation

  • Base Cases:
    • If the grid is empty or if the starting or ending cell has an obstacle, we return 0.
  • Memoization:
    • We use a dictionary called memo to store results of the smaller problems.
  • Recursive Calls:
    • The function calls itself for the cell below and the cell to the right.

Complexity Analysis

  • Time Complexity: O(m * n). Here, m is the number of rows, and n is the number of columns. This is because of memoization.
  • Space Complexity: O(m * n) for storing memoization.

This method makes the time needed much less compared to just using a simple recursive approach. It avoids calculating the same paths again. If you want to learn more about dynamic programming, you can check this article on Dynamic Programming - Fibonacci with Memoization.

Iterative Dynamic Programming Solution in Java for Unique Paths II

We will use an iterative dynamic programming method to solve the Unique Paths II problem. This method needs a 2D array to keep track of how many ways we can reach each cell in the grid. The grid can have obstacles, shown by 1, and free cells, shown by 0. Our aim is to find unique paths from the top-left corner to the bottom-right corner of the grid.

Java Implementation

Here is a simple Java code for the Unique Paths II problem using iterative dynamic programming:

public class UniquePathsII {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;

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

        // Create a DP array
        int[][] dp = new int[m][n];
        dp[0][0] = 1; // Start point

        // Fill the DP array
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // If the cell has an obstacle
                if (obstacleGrid[i][j] == 1) {
                    dp[i][j] = 0;
                } else {
                    // Sum paths from the top and left cells
                    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]; // Return the bottom-right cell value
    }
}

Explanation of the Code

  1. Initialization: We check if the starting or ending cell has an obstacle. If yes, we return 0.
  2. DP Array Setup: We make a dp array. Here, dp[i][j] shows the number of unique paths to the cell (i, j).
  3. Filling the DP Array:
    • We go through each cell in the grid.
    • If the cell is an obstacle, we set dp[i][j] to 0.
    • If it is a free cell, we add the number of paths from the cell above and the cell to the left.
  4. Return Result: The value in dp[m-1][n-1] gives the total unique paths to the bottom-right corner.

This method is good because it solves the problem in O(mn) time and uses O(mn) space. It works well for medium-sized grids. For more methods about dynamic programming, we can look at articles on Dynamic Programming: Simple Grid Path Sum or Unique Paths in a Grid.

Iterative Dynamic Programming Solution in Python for Unique Paths II

In the Unique Paths II problem, we need to find the number of unique paths from the top-left corner to the bottom-right corner of a grid. We have to go around obstacles. This solution uses a 2D list to keep track of how many ways we can reach each cell.

Python Implementation

Here is the Python code for the iterative dynamic programming solution for Unique Paths II:

def uniquePathsWithObstacles(obstacleGrid):
    if not obstacleGrid or obstacleGrid[0][0] == 1:
        return 0

    m, n = len(obstacleGrid), len(obstacleGrid[0])
    dp = [[0] * n for _ in range(m)]
    
    dp[0][0] = 1  # Starting point

    # 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 first row
    for j in range(1, n):
        dp[0][j] = dp[0][j-1] if obstacleGrid[0][j] == 0 else 0

    # Fill the rest of the dp array
    for i in range(1, m):
        for j in range(1, n):
            if obstacleGrid[i][j] == 0:  # If no obstacle
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
            else:
                dp[i][j] = 0  # If obstacle

    return dp[m-1][n-1]

Explanation of the Code

  • Initialization: We check if the grid is empty or if the starting point is blocked (value 1). If one of these is true, we return 0.
  • DP Table Setup: We make a 2D list dp to store the number of paths to each cell.
  • First Row and Column: We fill the first row and first column separately. They can only be reached from one side.
  • Filling the DP Table: For each cell in the grid, if there is no obstacle, the number of ways to reach it is the sum of the ways to reach the cell above it and the cell to the left.
  • Final Result: The value at dp[m-1][n-1] tells us how many unique paths there are to the bottom-right corner.

This iterative dynamic programming method has a time complexity of (O(m n)) and a space complexity of (O(m n)). Here, (m) and (n) are the sizes of the grid.

For more reading on dynamic programming, we can check articles like Dynamic Programming: Unique Paths in a Grid.

Iterative Dynamic Programming Solution in C++ for Unique Paths II

We can solve the Unique Paths II problem using an Iterative Dynamic Programming method. This method builds a 2D table, which we call the dp array. Each cell in this table shows the number of unique paths to that cell from the starting point. We start by setting up the table based on where the obstacles are. Then, we fill it up step by step using the values we calculated before.

Implementation Steps:

  1. Initialize the dp array: First, we create a 2D vector dp that is the same size as the input grid. We set all cells to 0 at first.
  2. Set the starting point: If the starting cell (0, 0) is not an obstacle, we set dp[0][0] = 1.
  3. Iterate through the grid: Next, for each cell, we update the dp table:
    • If the cell is an obstacle, we skip to the next cell.
    • For cells not in the first row or column, the number of paths to that cell is the sum of paths from the cell above and the cell to the left.
    • For cells in the first row or first column, we only add paths from one direction due to the edges.
  4. Result: The value in the bottom-right corner of the dp array (dp[m-1][n-1]) will show the total number of unique paths.

C++ Code Example:

#include <vector>

using namespace std;

int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
    int m = obstacleGrid.size();
    int n = obstacleGrid[0].size();
    
    vector<vector<int>> dp(m, vector<int>(n, 0));
    
    // Start point
    if (obstacleGrid[0][0] == 0) {
        dp[0][0] = 1;
    }
    
    // Fill dp array
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (obstacleGrid[i][j] == 1) {
                dp[i][j] = 0; // Obstacle cell
            } else {
                if (i > 0) dp[i][j] += dp[i - 1][j]; // From above
                if (j > 0) dp[i][j] += dp[i][j - 1]; // From left
            }
        }
    }
    
    return dp[m - 1][n - 1];
}

Key Points:

  • Time Complexity: O(m * n), where m is the number of rows and n is the number of columns.
  • Space Complexity: O(m * n) for the dp array. We can make this better to O(n) if we only keep the current and the previous row.
  • We need to think about edge cases like an obstacle at the starting point or the ending point.

This method helps us find the number of unique paths in a grid with obstacles using an iterative dynamic programming way in C++. If we want to learn more about dynamic programming, we can check out topics like Dynamic Programming - Unique Paths in a Grid.

Optimizing Space Complexity for Unique Paths II

In the Unique Paths II problem, we deal with a 2D grid. Some cells have obstacles. Our goal is to find how many unique paths go from the top-left corner to the bottom-right corner while avoiding obstacles. A simple dynamic programming method uses a 2D array to keep results for each cell. This can create high space usage.

To improve space usage, we can use a 1D array instead of a 2D array. The number of unique paths to any cell only depends on the current row and the row before it. So, we can lower the space needed from O(m * n) to O(n), where n stands for the number of columns.

Space Optimized Dynamic Programming Approach

  1. Initialization: We create a 1D array dp with size n and set all to 0. We set dp[0] to 1. There is one way to reach the first cell.

  2. Iterate through the grid:

    • For each row, we check if the cell has an obstacle.
    • If it has, we set dp[j] to 0. If it does not, we update dp[j] like this:
      • dp[j] += dp[j-1] for cells that are not in the first column.

  3. Result: The last element of dp holds the number of unique paths to the bottom-right corner.

Example Code in Java

public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    if (obstacleGrid == null || obstacleGrid.length == 0) return 0;
    int m = obstacleGrid.length, n = obstacleGrid[0].length;
    int[] dp = new int[n];
    dp[0] = obstacleGrid[0][0] == 0 ? 1 : 0;

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (obstacleGrid[i][j] == 1) {
                dp[j] = 0; // obstacle found
            } else if (j > 0) {
                dp[j] += dp[j - 1]; // update the dp array
            }
        }
    }
    return dp[n - 1]; // result is in the last cell
}

Example Code in Python

def uniquePathsWithObstacles(obstacleGrid):
    if not obstacleGrid or not obstacleGrid[0]: return 0
    m, n = len(obstacleGrid), len(obstacleGrid[0])
    dp = [0] * n
    dp[0] = 1 if obstacleGrid[0][0] == 0 else 0

    for i in range(m):
        for j in range(n):
            if obstacleGrid[i][j] == 1:
                dp[j] = 0  # obstacle found
            elif j > 0:
                dp[j] += dp[j - 1]  # update the dp array

    return dp[-1]  # result is in the last cell

Example Code in C++

int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
    if (obstacleGrid.empty() || obstacleGrid[0].empty()) return 0;
    int m = obstacleGrid.size(), n = obstacleGrid[0].size();
    vector<int> dp(n, 0);
    dp[0] = obstacleGrid[0][0] == 0 ? 1 : 0;

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (obstacleGrid[i][j] == 1) {
                dp[j] = 0; // obstacle found
            } else if (j > 0) {
                dp[j] += dp[j - 1]; // update the dp array
            }
        }
    }
    return dp[n - 1]; // result is in the last cell
}

By using a 1D array, we reduce space use while keeping our solution fast. We can use this method for other dynamic programming problems too. It helps save space without losing performance. For more reading on dynamic programming, you can check out the Dynamic Programming Unique Paths in a Grid.

Comparative Analysis of Different Approaches for Unique Paths II

When we solve the Unique Paths II problem, which involves a grid with obstacles, we can use different methods. Each method has its good and bad points. We will look at three main methods: Dynamic Programming, Recursive with Memoization, and Iterative Dynamic Programming.

1. Dynamic Programming Approach

  • Time Complexity: O(m * n). Here, m is the number of rows and n is the number of columns.
  • Space Complexity: O(m * n) for the DP table.

We use a 2D DP table to slowly build the number of unique paths to each cell while considering obstacles.

def uniquePathsWithObstacles(obstacleGrid):
    if not obstacleGrid or obstacleGrid[0][0] == 1: 
        return 0
    m, n = len(obstacleGrid), len(obstacleGrid[0])
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = 1

    for i in range(m):
        for j in range(n):
            if obstacleGrid[i][j] == 1:
                dp[i][j] = 0
            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]

2. Recursive Approach with Memoization

  • Time Complexity: O(m * n) because of memoization.
  • Space Complexity: O(m * n) for the recursion stack and memoization table.

This method uses recursion to check all paths. We save previous results to avoid doing the same work again.

def uniquePathsWithObstacles(obstacleGrid):
    m, n = len(obstacleGrid), len(obstacleGrid[0])
    memo = {}

    def dfs(x, y):
        if x < 0 or y < 0 or obstacleGrid[x][y] == 1:
            return 0
        if (x, y) == (0, 0):
            return 1
        if (x, y) in memo:
            return memo[(x, y)]

        memo[(x, y)] = dfs(x - 1, y) + dfs(x, y - 1)
        return memo[(x, y)]

    return dfs(m - 1, n - 1)

3. Iterative Dynamic Programming Solution

  • Time Complexity: O(m * n).
  • Space Complexity: O(n) if we use only one row.

This method fills a single array to show the current state of paths. It saves space by using the same array again.

public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    if (obstacleGrid[0][0] == 1) return 0;
    int m = obstacleGrid.length, n = obstacleGrid[0].length;
    int[] dp = new int[n];
    dp[0] = 1;

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (obstacleGrid[i][j] == 1) {
                dp[j] = 0;
            } else if (j > 0) {
                dp[j] += dp[j - 1];
            }
        }
    }
    return dp[n - 1];
}

Summary of Approaches

  • Dynamic Programming: Good for clear understanding but needs O(m * n) space.
  • Recursive with Memoization: It is easy to understand but may cause stack overflow for big grids.
  • Iterative Solution: It uses less space, good for big grids, and keeps O(m * n) time complexity.

Each method fits different situations based on the problem’s needs. For more knowledge about dynamic programming, we can check articles like Dynamic Programming: Fibonacci Number and more topics related.

Frequently Asked Questions

1. What is the Unique Paths II problem in dynamic programming?

The Unique Paths II problem is about finding how many unique paths are in a grid that can have obstacles. Each cell in the grid can be empty or have an obstacle. We use 0 for empty cells and 1 for obstacles. The goal is to find how many ways we can go from the top-left corner to the bottom-right corner while avoiding the obstacles. We can solve this problem well with dynamic programming.

2. How does the dynamic programming approach work for Unique Paths II?

In the dynamic programming approach for Unique Paths II, we make a 2D array. This array keeps track of the number of unique paths to each cell in the grid. We calculate the value of each cell by looking at the paths from the cell above it and the cell to its left. We also remember to check for obstacles. This method helps us find the paths quickly and does not make us calculate the same paths again. The time complexity is O(m*n), where m and n are the grid dimensions.

3. Can I use recursive memoization for solving Unique Paths II?

Yes, we can use a recursive method with memoization for Unique Paths II. In this way, a recursive function finds the number of unique paths from the current cell to the destination cell. We store results of paths we already calculated in a cache. This helps us avoid calculating the same paths again. So, we reduce the time complexity while we keep recursion easy.

4. How can I optimize space complexity in Unique Paths II?

To make space complexity better in Unique Paths II, we can use a one-dimensional array instead of a two-dimensional grid. We go through the grid and update the values in the array based on the paths from the previous row. This reduces the space needed from O(m*n) to O(n), where n is the number of columns. This trick is helpful for large grids.

5. What are the common mistakes to avoid when implementing Unique Paths II?

When we implement the Unique Paths II solution, we should avoid some common mistakes. One mistake is not handling edge cases like grids that start or end with obstacles. Another mistake is not setting up the dynamic programming array correctly. We must also check if the current cell is an obstacle. It is important to check the grid’s size and where the obstacles are before we run our algorithm. This way, we can avoid errors while the program runs. For more related dynamic programming tips, check our article on Dynamic Programming: Unique Paths in a Grid.