Practice/Microsoft/Leetcode 63. Unique Paths II

Leetcode 63. Unique Paths II

CodingMust

Problem

You are programming a delivery robot that navigates on a rectangular grid. The robot starts at the top-left corner and needs to reach the bottom-right corner to complete its delivery. The robot can only move either down or right at each step.

However, some cells in the grid contain obstacles that the robot cannot pass through. Your task is to calculate how many distinct paths exist from the starting position to the destination while avoiding all obstacles.

The grid is represented as a 2D array where 0 represents an open cell and 1 represents an obstacle.

Requirements

1. Return the total number of distinct valid paths from the top-left to the bottom-right corner
2. The robot can only move right or down (no diagonal, up, or left movements)
3. Cells containing obstacles (value 1) cannot be visited
4. If the start or end cell contains an obstacle, return 0
5. Handle edge cases including single-cell grids and fully blocked paths

Constraints

• m == obstacleGrid.length (number of rows)
• n == obstacleGrid[i].length (number of columns)
• 1 <= m, n <= 100
• obstacleGrid[i][j] is either 0 or 1
• The answer will fit in a 32-bit integer (guaranteed to be at most 2 × 10^9)

Examples

Example 1:

` Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]] Output: 2 Explanation: There are 2 ways to reach the bottom-right corner:

1. Right → Right → Down → Down
2. Down → Down → Right → Right The obstacle in the center blocks other potential paths. `

Example 2:

Input: obstacleGrid = [[0,1],[0,0]] Output: 1 Explanation: Only one path exists: Down → Right

Example 3:

Input: obstacleGrid = [[1,0]] Output: 0 Explanation: The starting cell is blocked, so no paths are possible.