C++ solution with 4ms time and O(n) space


  • 0
    C

    the first for-loop deal with the first row, then the next for-for-loop do the others.

    class Solution {
    public:
        int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
            vector<int> ret(obstacleGrid[0].size(), 0);
            for(int i=0; i<obstacleGrid[0].size(); i++){
                if(obstacleGrid[0][i]==1){
                    break;
                }
                ret[i] = 1;
            }
            
            for(int i=1; i<obstacleGrid.size(); i++){
                if(obstacleGrid[i][0]==1) ret[0]=0;
                for(int j=1; j<obstacleGrid[0].size(); j++){
                    if(obstacleGrid[i][j]==1) ret[j]=0;
                    else ret[j] += ret[j-1];
                }
            }
            return ret[obstacleGrid[0].size()-1];
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.