Unique Paths II (Robot Obstacles)

63.Unique Paths II

Array

Dynamic Programming

Matrix

Problem Statement:

A robot is located at the top-left corner of a m x n grid. 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. Now consider if some obstacles (marked as 1) are added to the grids. Return the number of unique paths.

Example:

Input:

obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]

→

Output:

2

Algorithm:

1. Use grid itself as DP array
2. Convert obstacles to 0 paths
3. Handle bottom and right edges
4. Sum paths from right and bottom

Complexity:

Time: O(m*n) | Space: O(1) since modifying input grid

Java Solution:

public int uniquePathsWithObstacles(int[][] grid) {
    int m = grid.length;
    int n = grid[0].length;
    
    for (int i = m - 1; i >= 0; i--) {
        for (int j = n - 1; j >= 0; j--) {
            if (grid[i][j] == 1)  // Obstacle: no paths possible
                grid[i][j] = 0;
            else if (i == m - 1 && j == n - 1)  // Bottom-right: one path
                grid[i][j] = 1;
            else if (i == m - 1)  // Bottom row: only right paths
                grid[i][j] = grid[i][j + 1];
            else if (j == n - 1)  // Right column: only down paths
                grid[i][j] = grid[i + 1][j];
            else  // Middle cells: sum of down and right paths
                grid[i][j] = grid[i + 1][j] + grid[i][j + 1];      
        }
    }
    
    return grid[0][0];  // Top-left contains total paths
}

Python Solution:

def uniquePathsWithObstacles(self, grid: List[List[int]]) -> int:
    m, n = len(grid), len(grid[0])
    
    for i in range(m-1, -1, -1):
        for j in range(n-1, -1, -1):
            if grid[i][j] == 1:  # Obstacle
                grid[i][j] = 0
            elif i == m-1 and j == n-1:  # Target
                grid[i][j] = 1
            elif i == m-1:  # Bottom row
                grid[i][j] = grid[i][j+1]
            elif j == n-1:  # Right column
                grid[i][j] = grid[i+1][j]
            else:  # Middle cells
                grid[i][j] = grid[i+1][j] + grid[i][j+1]
                
    return grid[0][0]

C++ Solution:

class Solution {
public:
    int uniquePathsWithObstacles(vectorint>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        
        for(int i = m-1; i >= 0; i--) {
            for(int j = n-1; j >= 0; j--) {
                if(grid[i][j] == 1)  // Found obstacle
                    grid[i][j] = 0;
                else if(i == m-1 && j == n-1)  // Target cell
                    grid[i][j] = 1;
                else if(i == m-1)  // Bottom row
                    grid[i][j] = grid[i][j+1];
                else if(j == n-1)  // Right column
                    grid[i][j] = grid[i+1][j];
                else  // Middle cells
                    grid[i][j] = grid[i+1][j] + grid[i][j+1];
            }
        }
        
        return grid[0][0];
    }
};