Java | TC: O(R*C) | SC: O(min(R,C)) | Space optimized Dynamic Programming solution
java\n/**\n * Space optimized Dynamic Programming solution (Input grid not modified)\n *\n * current cell = top cell + left cell. If there is an obstacle at cur
```java\n/**\n * Space optimized Dynamic Programming solution (Input grid not modified)\n *\n * current cell = top cell + left cell. If there is an obstacle at current cell,\n * then current cell = 0;\n *\n * Time Complexity: O(R * C).\n *\n * Space Complexity = O(min(R, C)). Either one column or one row is used for dp.\n *\n * R = Number of rows. C = Number of columns.\n */\nclass Solution {\n    public int uniquePathsWithObstacles(int[][] obstacleGrid) {\n        if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0].length == 0) {\n            return 0;\n        }\n\n        int rows = obstacleGrid.length;\n        int cols = obstacleGrid[0].length;\n        if (obstacleGrid[0][0] == 1 || obstacleGrid[rows - 1][cols - 1] == 1) {\n            return 0;\n        }\n        if (rows == 1 && cols == 1) {\n            return 1;\n        }\n\n        if (rows >= cols) {\n            return uniquePathHelper(obstacleGrid, rows, cols, true);\n        } else {\n            return uniquePathHelper(obstacleGrid, cols, rows, false);\n        }\n    }\n\n    private int uniquePathHelper(int[][] obstacleGrid, int big, int small, boolean isColsSmall) {\n        int[] dp = new int[small];\n        dp[0] = 1;\n        for (int i = 0; i < big; i++) {\n            if ((isColsSmall && obstacleGrid[i][0] == 1) || (!isColsSmall && obstacleGrid[0][i] == 1)) {\n                dp[0] = 0;\n            }\n            for (int j = 1; j < small; j++) {\n                if ((isColsSmall && obstacleGrid[i][j] == 1) || (!isColsSmall && obstacleGrid[j][i] == 1)) {\n                    dp[j] = 0;\n                    continue;\n                }\n                dp[j] += dp[j - 1];\n            }\n        }\n        return dp[small - 1];\n    }\n}\n```\n\n---\n\nSolutions to other parts of Unique Path question on LeetCode:\n- [62. Unique Paths](https://leetcode.com/problems/unique-paths/discuss/1513886/Java-or-TC:-O(M*N)-or-SC:-O(min(MN))-or-Space-optimized-Dynamic-Programming-solution)\n- [64. Minimum Path Sum](https://leetcode.com/problems/minimum-path-sum/discuss/1513899/Java-or-TC:-O(R*C)-or-SC:-O(min(RC))-or-Space-optimized-Dynamic-Programming-solution)\n- [980. Unique Paths III](https://leetcode.com/problems/unique-paths-iii/discuss/1513906/Java-or-TC:-O(3(R*C))-or-SC:-O(R*C)-or-DFS-solution-with-Backtracking)\n
['Array', 'Dynamic Programming', 'Matrix', 'Java']