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.lengthn == obstacleGrid[i].length1 <= m, n <= 100obstacleGrid[i][j] is 0 or 1.The Unique Paths II problem extends the classic grid path counting challenge by introducing obstacles in the matrix. The task is to determine how many unique ways a robot can move from the top-left to the bottom-right corner while only moving right or down, and avoiding blocked cells.
A common strategy is to use Dynamic Programming (DP). The idea is to build a dp matrix where each cell represents the number of ways to reach that position. If a cell contains an obstacle, the number of paths to that cell is 0. Otherwise, the value comes from the sum of paths from the cell above and the cell to the left.
Initialization is important: if the starting cell or any cell in the first row/column has an obstacle, all reachable cells after it in that direction become unreachable. The DP approach systematically fills the grid and produces the final answer at the destination cell. This method runs in O(m × n) time and can be optimized to O(n) space by using a single row array.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming (2D DP Table) | O(m × n) | O(m × n) |
| Dynamic Programming (Space Optimized) | O(m × n) | O(n) |
take U forward
Use these hints if you're stuck. Try solving on your own first.
Use dynamic programming since, from each cell, you can move to the right or down.
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.
Using dynamic programming, we can track the number of unique paths to each cell in the grid. Initialize a DP matrix of the same dimensions as the grid. If a cell contains an obstacle (value of 1), it will have 0 paths. Start from the top-left corner and accumulate the number of paths by adding the values from the cell above and the cell to the left, if they exist, taking into account obstacles.
Time Complexity: O(m * n), because each cell in the matrix is calculated once.
Space Complexity: O(m * n), for the DP table.
1#include <stdio.h>
2
3int uniquePathsWithObstacles(int** obstacleGrid, int m, int n) {
4 int dp[m][n]
This solution implements a dynamic programming strategy to fill a DP table. Each cell in the DP table represents the number of unique paths to that cell, calculated by summing the possible paths from the left and above cells, unless they contain obstacles.
Instead of using a full 2D DP array, we can optimize space by maintaining just a single row of size `n` to hold the number of paths to positions in the current row. Iterate over the grid, and update path counts by only storing the results for the current row, using the previous row information to calculate paths.
Time Complexity: O(m * n), iterating through the entire grid.
Space Complexity: O(n), only a single row is stored at a time.
1#
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
If a cell contains an obstacle, it cannot be part of any valid path. In the DP table, such cells are assigned a value of 0, meaning no paths can pass through them.
Yes, grid-based dynamic programming problems like Unique Paths II are commonly asked in FAANG and other top tech company interviews. They test a candidate’s ability to model states, handle edge cases like obstacles, and optimize space.
The optimal approach uses dynamic programming to count paths while avoiding obstacle cells. Each cell accumulates the number of ways to reach it from the top and left cells, provided they are not blocked. This ensures an efficient O(m × n) solution.
A 2D dynamic programming array or matrix is commonly used to store the number of paths to each grid cell. For space optimization, a single 1D array representing the current row can also be used while iterating through the grid.
Optimized C solution utilizes a single-dimension array to save space, updating path counts as it iterates over each grid row while handling obstacles.