Simple C++ explained solution with NO extra memory 6 ms


  • 0
    I

    This problem is a bit tricky as the grid is initialized with 1's for obstructions but 1 can also represent a valid number of paths to a given cell. So the idea is to reuse the original given grid but work with -ve numbers! In the first pass the first row and columns are initialized with -1 and if there are any obstructions we break.

    And after that we calculate the rest of the grid by by adding numbers from p[i-1][j] and p[i][j-1]

    ''''
    class Solution {
    public:

    // "og" is obstacle grid
    int uniquePathsWithObstacles(vector<vector<int>>& og) {
        if (!og.size())
          return 0;
        
        int m = og.size();
        int n = og[0].size();
        
        // if there is an obstruction at the destination return 0
        if (og[m-1][n-1] == 1)
           return 0;
        
        // Make first column "-1" and if there is an obstacle at a given cell, all cells after that 
        // will be 0s as they have already been initialized with 0s and there is no way to get there. Hence
       // the total number of paths to reach such cells is 0
        for (int i = 0; i < m; i++) {
            if (og[i][0] == 1) {
                break;
            }
            
            og[i][0] = -1;
        }
        
        // make first row -1 and if there is an obstacle break so the reaminder
        // of the column cells will be 0 as there is no way to get there
        for (int j = 0; j < n; j++) {
            if (og[0][j] == 1)
              break;
             
             og[0][j] = -1;
        }
        
        for (int i = 1; i < og.size(); i++) {
            for (int j = 1; j < og[i].size(); j++) {
                if (og[i][j] == 1)
                   continue;
                
                int paths = 0;
                if (og[i-1][j] != 1) {
                    paths += og[i-1][j];
                }
                
                if (og[i][j-1] != 1) {
                    paths += og[i][j-1];
                }
                
                og[i][j] = paths;
            }
            
        }
        
        return -1 * og[m-1][n-1];
    }
    

    };
    ''


Log in to reply
 

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