Unique Paths 2 — LeetCode
In this post, I would like to show you my algorithm to solve the Unique Paths 2 challenge on LeetCode.
The Problem states: 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 space is marked as 1 and 0 respectively in the grid.
Therefore, to understand it further we need to first think of what do we want to achieve. If the first column and first row where we see the picture of the Android equals to 1, this means there is no way to reach the star. Therefore, we just return nothing.
m = len(obstacleGrid)
n = len(obstacleGrid[0])if obstacleGrid[0][0] == 1:
return 0
Otherwise, by default we initialize the first row and first cell as 1, which means there is 1 way to start.
# Number of ways of reaching the starting cell = 1
obstacleGrid[0][0] == 1
Since we will iterate from left to right and top down, we will first iterate through the first column and assign either 0 or 1
for i in range(1, m):
obstacleGrid[i][0] = int(obstacleGrid[i][0] == 0 and obstacleGrid[i-1][0] == 1)
The same for the first row
# Filling the values for the first row
for j in range(1, n):
obstacleGrid[0][j] = int(obstacleGrid[0][j] == 0 and obstacleGrid[0][j-1] == 1)
Once this is done all we have to do is go through the row and column and calculate the value, after that the obstacleGrid[m-1][n-1] will have our answer.
Therefore:
for i in range(1,m):
for j in range(1,n):
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.
And this is what we have to return
return obstacleGrid[m-1][n-1]
I hope this helps to understand the problem and solution.
