Unique Paths II

The problem is to find the number of unique paths a robot can take to reach the bottom-right corner of a grid, considering some obstacles along the way. The robot can move either right or down, and an obstacle is represented by 1 in the grid, while a free space is represented by 0.

Here’s an explanation of how to solve this problem step by step:

Step 1: Handle Base Cases

First, check for the cases where the starting point or the ending point itself is an obstacle. If either of these is true, return 0 since there are no possible paths.

Step 2: Initialize a 2D DP Array

Create a 2D array dp of the same size as the obstacleGrid, to store the number of ways to reach each cell.

Step 3: Set Initial Values

Set dp[0][0] to 1 if obstacleGrid[0][0] is 0. Then, initialize the first row and first column based on the obstacles present in them.

Step 4: Iterate Through the Grid

Now, iterate through the remaining cells of the grid. For each cell, if it is not an obstacle, the number of ways to reach it is the sum of the number of ways to reach the cell above it and the cell to its left.

Here’s the code implementing these steps:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        if obstacleGrid[0][0] == 1 or obstacleGrid[-1][-1] == 1:
            return 0

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

        if obstacleGrid[0][0] == 0:
            dp[0][0] = 1

        for i in range(1, m):
            if obstacleGrid[i][0] == 0:
                dp[i][0] = dp[i - 1][0]

        for j in range(1, n):
            if obstacleGrid[0][j] == 0:
                dp[0][j] = dp[0][j - 1]

        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]

        return dp[-1][-1]

Key Takeaways

The problem is solved using dynamic programming.
We store the number of ways to reach each cell in a 2D array dp.
By handling obstacles properly, we calculate the number of unique paths to the destination.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
# @param {Integer[][]} obstacle_grid
# @return {Integer}
def unique_paths_with_obstacles(grid)
  rows = grid.size
  cols = grid[0].size  

  dp = Array.new(rows) { Array.new(cols, 0)}  
   
  if grid[0][0] == 0  
    dp[0][0] = 1
  else
    dp[0][0] = 0    
  end
    
  for i in (1...rows)
    if grid[i][0] == 1
      #          number of ways is one
      dp[i][0] = 0
    else
      dp[i][0] = dp[i-1][0]
    end
  end
   
  for i in (1...cols)
    if grid[0][i] == 1
      dp[0][i] = 0
    else
      dp[0][i] = dp[0][i-1]
    end
  end
    
  for i in (1...rows)
    for j in (1...cols)
      # path(m, n) = path(m-1, n) + path(m, n-1)
      if grid[i][j] == 0
        dp[i][j] = dp[i-1][j] + dp[i][j-1]
      else
        dp[i][j] = 0
      end
    end
  end
    
  dp[rows-1][cols-1]
end