Ex-Amazon explains a solution with Python, JavaScript, Java and C++
Intuition\nMain goal is to determine the count of unique paths from the top-left corner to the bottom-right corner of a grid while accounting for obstacles in t
# Intuition\nMain goal is to determine the count of unique paths from the top-left corner to the bottom-right corner of a grid while accounting for obstacles in the grid. It uses dynamic programming to iteratively calculate the paths, avoiding obstacles and utilizing previously computed values to efficiently arrive at the final count.\n\nThis python solution beats 96%.\n![Screen Shot 2023-08-12 at 21.13.22.png](https://assets.leetcode.com/users/images/74f201be-a679-4119-857c-162c270611f0_1691842439.115498.png)\n\n\n---\n\n# Solution Video\n## *** Please upvote for this article. *** \n# Subscribe to my channel from here. I have 244 videos as of August 12th\nhttp://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1\n\nhttps://youtu.be/-nVmLvqo5qc\n\n---\n\n# Approach\nThis is based on Python. Other might be different a bit.\n\n1. Define the class `Solution` which contains the method `uniquePathsWithObstacles` that takes `obstacleGrid` as input and returns the number of unique paths.\n\n2. Check if `obstacleGrid` is empty or if the starting cell (0, 0) is an obstacle (marked as 1). If either of these conditions is met, return 0, as there is no way to reach the destination.\n\n3. Get the number of rows and columns in the `obstacleGrid` and store them in `rows` and `cols` variables, respectively.\n\n4. Create an array `dp` of size `cols` to store the number of unique paths for each column. Initialize all values in `dp` to 0.\n\n5. Set `dp[0]` to 1, representing the number of ways to reach the starting cell (0, 0).\n\n6. Iterate through each row (`r`) in the `obstacleGrid`:\n\n   a. For each row, iterate through each column (`c`) in the `obstacleGrid`:\n\n      - If the current cell (`obstacleGrid[r][c]`) contains an obstacle (marked as 1), set `dp[c]` to 0, indicating that there are no paths to reach this obstacle cell.\n\n      - Otherwise, if the current cell is not an obstacle:\n\n        - Check if `c` is greater than 0 (i.e., not in the leftmost column). If true, update `dp[c]` by adding the value of `dp[c - 1]`. This accounts for the paths coming from the cell above (`dp[c]`) and the cell to the left (`dp[c - 1]`).\n\n7. After iterating through all the cells in the grid, return the value of `dp[cols - 1]`, which represents the number of unique paths to reach the bottom-right cell (rows - 1, cols - 1).\n\nIn summary, this algorithm uses dynamic programming to calculate the number of unique paths from the top-left corner to the bottom-right corner of the grid while avoiding obstacles. The `dp` array is updated iteratively, taking into account the paths from the cell above and the cell to the left.\n\n# How solution code works\n`[0, 0, 0]`\n`[0, 1, 0]`\n`[0, 0, 0]`\n\nBefore starting nested loop, `dp` is `[1, 0, 0]`.\n\n1. iterating the first row and using `[1, 0, 0]`(previous result). In the end dp should be `[1, 1, 1]`\n    - check `uniquePathsWithObstacles[0][0]` \u2192 `dp = [1, 0, 0]`\n    - check `uniquePathsWithObstacles[0][1]` \u2192 `dp = [1, 1, 0]`\n    - check `uniquePathsWithObstacles[0][2]` \u2192 `dp = [1, 1, 1]`\n\n2. iterating the second row and using `[1, 1, 1]`(previous result). In the end dp should be `[1, 0, 1]`\n    - check `uniquePathsWithObstacles[1][0]` \u2192 `dp = [1, 1, 1]`\n    - check `uniquePathsWithObstacles[1][1]` \u2192 `dp = [1, 0, 1]`\n    - check `uniquePathsWithObstacles[1][2]` \u2192 `dp = [1, 0, 1]`\n\n3. iterating the thrid row and using `[1, 0, 1]`(previous result). In the end dp should be `[1, 1, 2]`\n    - check `uniquePathsWithObstacles[2][0]` \u2192 `dp = [1, 0, 1]`\n    - check `uniquePathsWithObstacles[2][1]` \u2192 `dp = [1, 1, 1]`\n    - check `uniquePathsWithObstacles[2][2]` \u2192 `dp = [1, 1, 2]` \n\nOutput should be `2`.\n\n# Complexity\n- Time complexity: O(rows * cols)\n\n- Space complexity: O(cols)\n\n```python []\nclass Solution:\n    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:\n        if not obstacleGrid or obstacleGrid[0][0] == 1:\n            return 0\n\n        rows, cols = len(obstacleGrid), len(obstacleGrid[0])\n        dp = [0] * cols\n        dp[0] = 1\n\n        for r in range(rows):\n            for c in range(cols):\n                if obstacleGrid[r][c] == 1:\n                    dp[c] = 0\n                else:\n                    if c > 0:\n                        dp[c] += dp[c - 1]\n\n        return dp[cols - 1] \n```\n```javascript []\n/**\n * @param {number[][]} obstacleGrid\n * @return {number}\n */\nvar uniquePathsWithObstacles = function(obstacleGrid) {\n    if (!obstacleGrid || obstacleGrid[0][0] === 1) {\n        return 0;\n    }\n\n    const rows = obstacleGrid.length;\n    const cols = obstacleGrid[0].length;\n    const dp = new Array(cols).fill(0);\n    dp[0] = 1;\n\n    for (let r = 0; r < rows; r++) {\n        for (let c = 0; c < cols; c++) {\n            if (obstacleGrid[r][c] === 1) {\n                dp[c] = 0;\n            } else {\n                if (c > 0) {\n                    dp[c] += dp[c - 1];\n                }\n            }\n        }\n    }\n\n    return dp[cols - 1];    \n};\n```\n```java []\nclass Solution {\n    public int uniquePathsWithObstacles(int[][] obstacleGrid) {\n        if (obstacleGrid == null || obstacleGrid[0][0] == 1) {\n            return 0;\n        }\n\n        int rows = obstacleGrid.length;\n        int cols = obstacleGrid[0].length;\n        int[] dp = new int[cols];\n        dp[0] = 1;\n\n        for (int r = 0; r < rows; r++) {\n            for (int c = 0; c < cols; c++) {\n                if (obstacleGrid[r][c] == 1) {\n                    dp[c] = 0;\n                } else {\n                    if (c > 0) {\n                        dp[c] += dp[c - 1];\n                    }\n                }\n            }\n        }\n\n        return dp[cols - 1];        \n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {\n        if (obstacleGrid.empty() || obstacleGrid[0][0] == 1) {\n            return 0;\n        }\n\n        int rows = obstacleGrid.size();\n        int cols = obstacleGrid[0].size();\n        vector<int> dp(cols, 0);\n        dp[0] = 1;\n\n        for (int r = 0; r < rows; r++) {\n            for (int c = 0; c < cols; c++) {\n                if (obstacleGrid[r][c] == 1) {\n                    dp[c] = 0;\n                } else {\n                    if (c > 0) {\n                        dp[c] += dp[c - 1];\n                    }\n                }\n            }\n        }\n\n        return dp[cols - 1];        \n    }\n};\n```\n\n# Related video\nI have an video for Unique Path I. Please check if you like.\n\nhttps://youtu.be/6NorAYw7NMU\n\nThank you for reading. Please upvote this article and don\'t forget to subscribe to my youtube channel!\n
['C++', 'Java', 'Python3', 'JavaScript']