Unique Paths II

Unique Paths II is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Dynamic Programming (DP) Patterns pattern, in the 2D Array (Unique Paths on Grid) subpattern.

Problem statement

You are given an m x n integer array grid. There is a robot initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle.

Return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The testcases are generated so that the answer will be less than or equal to 2 109.

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.

Topics and companies

Topics: Array, Dynamic Programming, Matrix.

Reported in interviews at Amazon, Bloomberg, Facebook, Microsoft.

How to practise Unique Paths II on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(m * n), where m is the number of rows and n is the number of columns. Each cell is visited exactly once. time and O(m * n) for the DP table. (Can be optimized to O(n) with a 1D array, but this uses a 2D array for clarity.) space.

Open Unique Paths II in the code editor, or read the Unique Paths II editorial for a worked solution with its approach and complexity analysis.

Where Unique Paths II sits in the DSA pattern sheet

Problems related to Unique Paths II

Other problems that use the same 2D Array (Unique Paths on Grid) and Dynamic Programming (DP) Patterns techniques:

Preparing this workspace.