63. Unique Paths II

1. Description

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 * $10^9$.

2. Example

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

3. Constraints

• m == obstacleGrid.length
• n == obstacleGrid[i].length
• 1 <= m, n <= 100
• obstacleGrid[i][j] is 0 or 1.

4. Solutions

Dynamic Programming

m = grid.size(), n = grid.front().size()
Time complexity : O(mn)
Space complexity : O(n)

class Solution {
public:
    int uniquePathsWithObstacles(const vector<vector<int>> &grid) {
        const int m = grid.size(), n = grid.front().size();

        vector<int> path_count(n, 0);
        path_count[0] = 1;
        for (int i = 0; i < m; ++i) {
            if (grid[i][0] == 1) {
                path_count[0] = 0;
            }

            for (int j = 1; j < n; ++j) {
                if (grid[i][j] == 0) {
                    path_count[j] += path_count[j - 1];
                } else {
                    path_count[j] = 0;
                }
            }
        }

        return path_count.back();
    }
};