O(n^2) time / O(n) space c++ solution


  • 0

    it's pretty familiar with the uniquePath solution, with some extra consideration

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

Log in to reply
 

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