63. Unique Paths II

Unique Paths II (LeetCode 63) 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.

• NeetCode 250 · #192 of 250 · 2-D Dynamic Programming

How to solve Unique Paths II

Unique Paths II is a Unique Paths on Grid problem, part of Dynamic Programming (DP) Patterns. Count paths and find optimal paths in grids using 2D dynamic programming.

Work towards the solution in these steps:

1. Use dynamic programming since, from each cell, you can move to the right or down.
2. assume dp[i][j] is the number of unique paths to reach (i, j). dp[i][j] = dp[i][j -1] + dp[i - 1][j]. Be careful when you encounter an obstacle. set its value in dp to 0.

The reference solution runs in O(m * n) time and O(m * n) space.

The Unique Paths II solution and editorial walks through the full approach with reference code.

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) time and O(m * n) 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

• Dynamic Programming (DP) Patterns pattern guide
• 2D Array (Unique Paths on Grid) subpattern
• The full DSA patterns 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:

• Count Square Submatrices with All Ones — Medium, same subpattern
• Interleaving String — Medium, same subpattern
• Longest Increasing Path in a Matrix — Hard, same subpattern
• Maximal Square — Medium, same subpattern
• Minimum Falling Path Sum — Medium, same subpattern
• Minimum Path Sum — Medium, same subpattern

Unique Paths II FAQ