LeetCode 63. Unique Paths II

Description

https://leetcode.com/problems/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 space is marked as 1 and 0 respectively in the grid.

Example 1:

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

Example 2:

Input: obstacleGrid = [[0,1],[0,0]]
Output: 1

Constraints:

• m == obstacleGrid.length
• n == obstacleGrid[i].length
• 1 <= m, n <= 100
• obstacleGrid[i][j] is 0 or 1.

Explanation

Follow up question for Unique Paths. We can still use a two-dimensional array to show the number of unique paths to each square on the grid.

The number of unique paths to each square on the first column would be 1 if the square is not an obstacle. If the square is an obstacle, the square and the remaining squares on the first column would be 0.

The number of unique paths to each square on the first row would be 1 if the square is not an obstacle. If the square is an obstacle, the square and the remaining squares on the first row would be 0.

The number of unique paths to the squares not at the first row or first column would be the sum of the number of unique paths to its previous left square and top square if the square is not an obstacle. If the square is an obstacle, the unique path would be just 0.

Java Solution

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0].length == 0) {
            return 0;
        }
        
        int height = obstacleGrid.length;
        int width = obstacleGrid[0].length;
        
        int[][] paths = new int[height][width];
        
        // first column
        for (int i = 0; i < height; i++) {
            if (obstacleGrid[i][0] != 1) {
                paths[i][0] = 1;
            } else {
                break;
            }
        }
        
        // first row
        for (int j = 0; j < width; j++) {
            if (obstacleGrid[0][j] != 1) {
                paths[0][j] = 1;
            } else {
                break;
            }
        }
        
        // for spaces not at first row or first column
        for (int i = 1; i < height; i++) {
            for (int j = 1; j < width; j++) {
                if (obstacleGrid[i][j] != 1) {
                    paths[i][j] = paths[i - 1][j] + paths[i][j - 1];
                }                
            }
        }
        
        return paths[height - 1][width - 1];
    }
}

Python Solution

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        
        paths = [[0 for j in range(n)] for i in range(m)]
        
                
        for i in range(m):
            if obstacleGrid[i][0] != 1:
                paths[i][0] = 1
            else:
                break

        for j in range(n):
            if obstacleGrid[0][j] != 1:
                paths[0][j] = 1
            else:
                break

        print (paths)
        
        for i in range(1, m):        
            for j in range(1, n):
                if obstacleGrid[i][j] == 1:
                    paths[i][j] = 0
                else:
                    paths[i][j] = paths[i - 1][j] + paths[i][j - 1]        
        
        return paths[m - 1][n - 1]
                

• Time Complexity: O(MN).
• Space Complexity: O(MN).