In today’s post, we’ll talk about the Unique Paths II problem from Leetcode.
If you have yet to check out our previous post on the Unique Paths problem, you should check it out first as today’s solution is similar to the first approach we used for that challenge.
Table of Contents
The Unique Paths II Problem
Let’s discuss the problem for today’s challenge.
Similar to the Unique Paths problem, the problem for today requires you to determine the number of ways to get from the top-left corner of a 2D grid to the bottom-right corner, given that you are only allowed to move right or move down.
However, for the Unique Paths II problem, obstacles are added to the grid and you are not allowed to access any cell with an obstacle.
Your job is to write a function called uniquePathsWithObstacles() that has one parameter – obstacleGrid.
obstacleGrid is a list of list that consists of 0s and 1s. A 0 indicates that there’s no obstacle for that cell, while a 1 indicates an obstacle.
For instance, the following grid (where X denotes an obstacle)
is represented as
obstacleGrid = [[0, 0, 1, 0, 1],[0, 0, 0, 1, 0], [1, 0, 0, 1, 0], [0, 0, 0, 0, 0]]
Your job is to determine the number of ways to travel from the top-left corner of the grid to the bottom-right corner, without passing by any cell with an obstacle.
Suggested Approach
The approach that we’ll take for the Unique Paths II problem is similar to the first approach for the Unique Paths problem.
We’ll iterate through obstacleGrid and update its cells such that each cell stores the number of ways to reach that cell.
Suppose we have
obstacleGrid = [[0, 0, 1, 0, 1],[0, 0, 0, 1, 0], [1, 0, 0, 1, 0], [0, 0, 0, 0, 0]]
Before updating, the values in the cells indicate whether there’s an obstacle at a particular cell.
After updating, the values represent the number of ways to reach a particular cell.
The point above is very important to bear in mind. Before updating, 1 indicates that a certain cell has an obstacle. After updating, 1 indicates that there is 1 way to reach a certain cell.
Let’s look at the steps needed for today’s approach:
Step 1: Update The First Row In The Grid
First, we need to update the first row in the grid. In order to do that, we need to understand that there is at most 1 way to reach any cell in that row (as we can only move right or move down).
For instance, for the grid below, the only way to reach cell D is to use the path A -> B -> C -> D.
In order to reach cell D, two conditions must be fulfilled:
- Firstly, there cannot be any obstacle at cell D itself.
- Secondly, we must be able to reach the cells before cell D. In other words, we must be able to reach cells A, B and C. Suppose there is an obstacle at cell C, it will be impossible to reach cell D as we must pass by cell C in order to reach cell D.
As such, we can update the first row using the rule below:
If there’s an obstacle at cell i, or if the cell on its left is inaccessible, set cell i to 0 (i.e. it’s impossible to reach cell i). Else, set cell i to 1 (i.e. there is one way to reach cell i).
Step 2: Update The First Column In The Grid
After updating the first row, we proceed to update the first column in the grid, starting from the second row.
To update the first column, we need to understand that there is also at most 1 way to reach any cell in that column. For instance, to reach cell K in the grid above, we can only use the path A -> F -> K.
As such, we can conclude that in order to reach any cell in the first column, two conditions must be satisfied:
- There must be no obstacle in the cell itself.
- The cells above it must be accessible.
Based on these two conditions, we can update the first column using the following rule:
If there’s an obstacle at cell i, or if the cell above is inaccessible, set cell i to 0 (i.e. it’s impossible to reach cell i). Else, set cell i to 1 (i.e. there is one way to reach cell i).
Step 3: Update The Remaining Cells
After updating the first row and column, we are ready to update the remaining cells. This step is similar to Step 3 in the Unique Paths problem solution (approach 1).
Given that we can only move right or move down, we conclude that in order to reach any of the remaining cells, we must either go via the cell above it, or the cell on its left.
For instance, to reach cell N in the grid above, we must pass by either cell I (e.g. A -> B -> C -> D -> I -> N) or cell M (e.g. A -> B -> G -> H -> M -> N).
Hence, the number of ways to reach any of the remaining cells is given by the sum of the number of ways to reach the cell above it and the cell on its left.
For instance, with reference to our grid above, if there are 4 ways to reach cell I and 6 ways to reach cell M, there are 4 + 6 = 10 ways to reach cell N (4 of which pass through cell I and 6 pass through cell M). This is assuming that cell N itself is accessible (i.e. there is no obstacle at cell N).
As such, we can update the remaining cells using the following rule:
If there’s an obstacle at cell i, set cell i to 0 (i.e. it’s impossible to reach cell i). Else, set cell i to the sum of the cell above it and the cell on its left.
Step 4: Return The Value Of The Last Cell
After updating all the cells in the grid, the last cell stores the answer that we need. Hence, we simply return its value and the function is complete.
Based on the description above, try working on this challenge yourself.
Graphical Illustration
Suggested Solution
The suggested solution for the Unique Paths II problem in Python is as follows:
def uniquePathsWithObstacles(obstacleGrid):
if obstacleGrid[0][0] == 1:
return 0
else:
obstacleGrid[0][0] = 1
m = len(obstacleGrid)
n = len(obstacleGrid[0])
# Update first row
i = 1
while i < n:
if obstacleGrid[0][i] == 0 and obstacleGrid[0][i-1] == 1:
obstacleGrid[0][i] = 1
else:
obstacleGrid[0][i] = 0
i += 1
# Update first column
i = 1
while i < m:
if obstacleGrid[i][0] == 0 and obstacleGrid[i-1][0] == 1:
obstacleGrid[i][0] = 1
else:
obstacleGrid[i][0] = 0
i += 1
# Update remaining cells
for i in range(1, m):
for j in range(1, n):
if obstacleGrid[i][j] == 1:
obstacleGrid[i][j] = 0
else:
obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1]
# Return result for last cell
return obstacleGrid[-1][-1]Here, we first define a function called uniquePathsWithObstacles() that has one parameter – obstacleGrid.
Inside the function, we check if there’s an obstacle at the top-left cell. If there is, it is impossible to proceed to any of the other cells. Hence, we return 0 (i.e. it is impossible to reach the bottom-right cell). If there is no obstacle at the top-left cell, we update its value to 1.
Determining The Dimensions Of The Grid
Next, we use the len() function to determine the number of elements in obstacleGrid (on line 8) and assign the result to a variable called m. This represents the number of rows in the grid.
We also use the len() function to determine the number of elements in the first nested list in obstacleGrid and assign the result to a variable called n. This represents the number of columns in the grid.
Updating The First Row
After getting the dimensions of the grid, we use a while loop (from lines 12 to 19) to update the first row.
Inside the while loop, we use an if statement to check the following conditions:
- Is the current cell free of obstacle (i.e.
obstacleGrid[0][i] == 0?) and - Is the cell on the left of the current cell accessible (i.e.
obstacleGrid[0][i-1] == 1?)
If both conditions return True, we set obstacleGrid[0][i] to 1. This indicates that there is 1 way to reach the current cell.
Else, we set it to 0, indicating that the current cell is inaccessible.
Updating The First Column
After updating the first row, we proceed to update the first column using the while loop from lines 23 to 29. This loop follows the same logic as the previous loop and should be quite self-explanatory.
Updating The Remaining Cells
After updating the first row and column, we proceed to update the remaining cells. To do that, we use the for loop from lines 32 to 37.
Inside the loop, we check if there’s any obstacle at the current cell. If there is, the if condition on line 34 evaluates to True and we set obstacleGrid[i][j] to 0 (to indicate that the current cell is inaccessible).
Else, we set it to the sum of obstacleGrid[i-1][j] (the cell above) and obstacleGrid[i][j-1] (the cell on its left).
Returning The Value Of The Last Cell
After iterating and updating all the cells in the grid, we return the value of the last cell (i.e. the bottom-right cell) on line 40. With that, the function is complete.