algoadvance

A robot is located at the top-left corner of an 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 that some obstacles are added to the grids. How many unique paths would there be?

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

You need to implement a function uniquePathsWithObstacles(obstacleGrid: List[List[int]]) -> int that takes a 2D array obstacleGrid and returns the number of unique paths from the top-left to the bottom-right corner.

Example 1:

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

Example 2:

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

Clarifying Questions

  1. Single Cell Grid: What if the grid is a single cell with an obstacle?
    • If it’s an obstacle the answer is 0, otherwise 1.
  2. All Obstacles: What if the path is completely blocked?
    • The result should be 0 since no path exists.

Strategy

  1. Initialization: Start from the top-left corner. If the starting point itself is an obstacle, return 0.
  2. DP Table: Use a 2D DP table where dp[i][j] represents the number of unique paths to position (i, j).
  3. Transition: For each cell, calculate paths from the top (i-1, j) and left (i, j-1), but only if they are not obstacles.
  4. Base Case: Set dp[0][0] to 1 if there’s no obstacle at start, else 0.
  5. Boundary Conditions: Ensure to handle case where rows or columns are just obstacles.

Time Complexity

Code

Here’s how you can solve it in Python:

from typing import List

def uniquePathsWithObstacles(obstacleGrid: List[List[int]]) -> int:
    if not obstacleGrid:
        return 0
    
    m, n = len(obstacleGrid), len(obstacleGrid[0])
    
    # If the starting or ending point is an obstacle, return 0
    if obstacleGrid[0][0] == 1 or obstacleGrid[m - 1][n - 1] == 1:
        return 0
    
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = 1
    
    for i in range(m):
        for j in range(n):
            if obstacleGrid[i][j] == 1:
                dp[i][j] = 0
            else:
                if i > 0:
                    dp[i][j] += dp[i - 1][j]
                if j > 0:
                    dp[i][j] += dp[i][j - 1]
    
    return dp[m - 1][n - 1]

This code initializes the DP table, handles the boundary conditions carefully, and iterates through the grid to fill out the number of unique paths taking into account obstacles.

Try our interview co-pilot at AlgoAdvance.com