0 ms || 100% faster Java solution || 2 ways || DP and No extra space
Approach 1 : Using Dynamic Programming\n Describe your first thoughts on how to solve this problem. \nFor every cell that is not an obstacle,\nThe number of way
# Approach 1 : Using Dynamic Programming\n<!-- Describe your first thoughts on how to solve this problem. -->\nFor every cell that is not an obstacle,\nThe number of ways to reach it is the sum of\n`Number of ways to reach the cell to its left`\nAnd `the number of ways to reach the cell above it`\n\n`ways[row][column]` = `ways[row - 1][column]` + `ways[row][column - 1]`\n\n\n# Complexity\n- Time complexity: $$O(M * N)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(M * N)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n![Screenshot (3903).png](https://assets.leetcode.com/users/images/81a61705-4980-4d59-802d-393543a5383d_1691837260.698575.png)\n```java []\nclass Solution // 100.00% faster, 0 ms solution\n{\n    public int uniquePathsWithObstacles(int[][] obstacleGrid) \n    {\n        int m = obstacleGrid.length, n = obstacleGrid[0].length;\n        int dp[][] = new int [m+1][n+1];\n        if(obstacleGrid[0][0] != 1)\n        dp[1][1] = 1;\n        for (int i = 1; i <= m; i++)\n            for (int j = 1; j <= n; j++)\n                if (obstacleGrid[i - 1][j - 1] != 1)\n                    dp[i][j] += dp[i - 1][j] + dp[i][j - 1];\n        return dp[m][n];\n    }\n}\n```\n```cpp []\n// Runtime: 0 ms, faster than 100.00% of C++ online submissions for Unique Paths II.\n// Memory Usage: 7.9 MB, less than 25.25% of C++ online submissions for Unique Paths II.\nclass Solution\n{\npublic:\n    int uniquePathsWithObstacles(vector<vector<int>> &obstacleGrid)\n    {\n        int m = obstacleGrid.size(), n = obstacleGrid[0].size();\n        // If the starting point is an obstacle\n        // there is no way to reach th e bottom- right cell\n        if (obstacleGrid[0][0] == 1)\n            dp[1][1] = 1;\n        // Set the starting point as 1\n        // Always 1 way to reach this cell, in case its not an obstacle\n        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));\n        for (int i = 1; i <= m; i++)\n            for (int j = 1; j <= n; j++)\n                if (obstacleGrid[i - 1][j - 1] != 1)\n                    dp[i][j] += dp[i - 1][j] + dp[i][j - 1];\n        return dp[m][n];\n    }\n};\n```\n\n# Approach 2 : No extra Space\n\n# Complexity\n- Time complexity: $$O(M * N)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(1)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n```cpp []\nclass Solution // Runtime: 3 ms, faster than 80.74% of C++ online submissions for Unique Paths II.\n               // Memory Usage: 7.5 MB, less than 90.13% of C++ online submissions for Unique Paths II.\n{\npublic:\n    int uniquePathsWithObstacles(vector<vector<int>> &obstacleGrid)\n    {\n        // If the starting cell is an obstacle\n        // There will be no way to reach the bottom-right cell\n        // Hence return 0\n        if (obstacleGrid[0][0])\n            return 0;\n        // For any given cell best a robot can do is to\n        // Go down or go right\n        int n = obstacleGrid.size(), m = obstacleGrid[0].size();\n        obstacleGrid[0][0] = 1;\n\n        for (int i = 1; i < m; i++)     // For the top row, cells can only be reached from the left (previous column)\n            // if at (i,j) obstacle is present, set it to 0 ===> No contribution\n            // Otherwise Set it equal the cell just left of it\n            obstacleGrid[0][i] = (obstacleGrid[0][i] == 0) ? obstacleGrid[0][i - 1] : 0;\n\n        for (int i = 1; i < n; i++) \n        // Similarily for the leftmost column, only way to travel is down\n        // And therefore it can only be reached from the up (previous row)\n        obstacleGrid[i][0] = (obstacleGrid[i][0] == 0) ? obstacleGrid[i - 1][0] : 0;\n\n        for (int i = 1; i < n; i++)     // For any other cell, the number of ways to reach it is equal to the number of ways to\n            for (int j = 1; j < m; j++) // reach the cell to its left and the cell above it\n                if (obstacleGrid[i][j]) // if at (i,j) obstacle is present, set it to 0 ===> No contribution\n                    obstacleGrid[i][j] = 0;\n                else                                                                      // The number of ways to reach the cell is equal to the number of ways to\n                    obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1]; // reach the cell above it + the number of ways to reach the cell to its left\n\n        return obstacleGrid[n - 1][m - 1];\n    }\n};\n```\n\n![upvote.png](https://assets.leetcode.com/users/images/d077ccad-9321-4c34-a4a8-b8b79ffd4031_1691838956.8384304.png)\n\n\n
['Array', 'Dynamic Programming', 'C++', 'Java']