Unique Paths II

​A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below). Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

Note: m and n will be at most 100.

Example 1:

Input:
[
  [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

This is an extension of Find Unique Paths I. The robot can only move either down or right. Hence any cell in the first row can only be reached from the cell left to it. And, any cell in the first column can only be reached from the cell above it.

ALGORITHM:

  1. If the first cell obstacleGrid[0,0] contains 1, this means there is an obstacle in the first cell. Hence the robot won’t be able to make any move.
  2. Iterate the first Row. Set a value 1 to all the cells unless you get an obstacle. If we get an obstacle then set a value 0 to this cell along with all subsequent cells.
  3. Iterate the first Column. Set a value 1 to all the cells unless you get an obstacle. If we get an obstacle then set a value 0 to this cell along with all subsequent cells.
  4. We can use a boolean flag to track, if an obstacle is found or not during iteration. 
  5. Now, iterate through the array starting from cell obstacleGrid[1,1]. If a cell originally doesn’t contain any obstacle then the number of ways of reaching that cell would be the sum of the number of ways of reaching the cell above it and number of ways of reaching the cell to the left of it.
    1. obstacleGrid[i,j] = obstacleGrid[i-1,j] + obstacleGrid[i,j-1]
  6. If a cell contains an obstacle set it to 0 and continue. This is done to make sure it doesn’t contribute to any other path.
class UniquePathIISolution {

  public int uniquePathsWithObstacles(int[][] obstacleGrid) {

    // If the starting cell has an obstacle, then simply return
    // as there would be no paths to the destination.
    if (obstacleGrid[0][0] == 1) {
      return 0;
    }
    int rows = obstacleGrid.length;
    int columns = obstacleGrid[0].length;

    // Filling the values for the first column
    boolean obstacleFound = false;
    for (int i = 0; i < rows; i++) {
      if (obstacleGrid[i][0] == 0 && !obstacleFound) {
        obstacleGrid[i][0] = 1;
      } else {
        obstacleGrid[i][0] = 0;
        obstacleFound = true;
      }
    }

    // Filling the values for the first row
    obstacleFound = false;
    for (int i = 1; i < columns; i++) {
      if (obstacleGrid[0][i] == 0 && !obstacleFound) {
        obstacleGrid[0][i] = 1;
      } else {
        obstacleGrid[0][i] = 0;
        obstacleFound = true;
      }
    }

    // Starting from cell(1,1) fill up the values
    // No. of ways of reaching cell[i][j] = cell[i - 1][j] + cell[i][j - 1]
    // i.e. From above and left.
    for (int i = 1; i < rows; i++) {
      for (int j = 1; j < columns; j++) {
        if (obstacleGrid[i][j] == 0) {
          obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
        } else {
          obstacleGrid[i][j] = 0;
        }
      }
    }
    // Return value stored in rightmost bottommost cell. That is the destination.
    return obstacleGrid[rows - 1][columns - 1];
  }
}

public class UniquePathII {
  public static void main(String[] args) {
    int[][] obstacleGrid = {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}};
    UniquePathIISolution solution = new UniquePathIISolution();
    System.out.println("No of paths :" + solution.uniquePathsWithObstacles(obstacleGrid));
  }
}

Complexity Analysis

  • Time Complexity: O(M×N). The rectangular grid given to us is of size M×N and we process each cell just once.
  • Space Complexity: O(1). We are utilizing the obstacleGrid as the DP array. Hence, no extra space.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s