How to solve Leetcode 63. Unique Paths II

Dynamic programming in place

·

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 test cases are generated so that the answer will be less than or equal to `2 * 10^9`.

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`.

Solution: Dynamic programming in place

Let us find the relationship between the positions.

If there is no obstacle at position `(row = i, col = j)`, the number of paths `np[i][j]` that the robot can take to reach this position is:

``````np[i][j] = np[i - 1][j] + np[i][j - 1]
``````
• As long as there is no obstacle in the first row, `np[0][j] = 1`. Otherwise, `np[0][k] = 0` for all `k >= j0`, where `(0, j0)` is the position of the first obstacle in the first row.

• Similarly, as long as there is no obstacle in the first column, `np[i][0] = 1`. Otherwise, `np[k][0] = 0` for all `k >= i0`, where `(i0, 0)` is the position of the first obstacle in the first column.

Code

``````#include <vector>
#include <iostream>
using namespace std;
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
const int row = obstacleGrid.size();
const int col = obstacleGrid[0].size();
vector<vector<int>> np(row, vector<int>(col, 0));
for (int i = 0; i < row && obstacleGrid[i][0] == 0; i++) {
np[i][0] = 1;
}
for (int j = 0; j < col && obstacleGrid[0][j] == 0; j++) {
np[0][j] = 1;
}
for (int i = 1; i < row; i++) {
for (int j = 1; j < col; j++) {
if (obstacleGrid[i][j] == 0) {
np[i][j] = np[i - 1][j] + np[i][j - 1];
}
}
}
return np[row - 1][col - 1];
}
int main() {
vector<vector<int>> obstacleGrid = {{0,0,0},{0,1,0},{0,0,0}};
cout << uniquePathsWithObstacles(obstacleGrid) << endl;
obstacleGrid = {{0,1},{0,0}};
cout << uniquePathsWithObstacles(obstacleGrid) << endl;
}
``````
``````Output:
2
1
``````

Complexity

• Runtime: `O(m*n)`, where `m x n` is the size of the `grid`.

• Extra space: `O(m*n)`.

References

Get my FREE book "10 Classic Coding Challenges"