Best O(M*N) Solution
Approach 1\nRecursion (TLE)\n\n# Complexity\n- Time complexity:\nO(2^S) --> S = m * n\n\n- Space complexity:\nO(m + n)\n\n# Code\n\nclass Solution {\nprivate:\n
# Approach 1\nRecursion (TLE)\n\n# Complexity\n- Time complexity:\n$$O(2^S)$$ --> S = m * n\n\n- Space complexity:\n$$O(m + n)$$\n\n# Code\n```\nclass Solution {\nprivate:\n    int solve(int row, int col, vector<vector<int>>& obstacleGrid) {\n        if (row >= 0 && col >= 0 && obstacleGrid[row][col] == 1)\n            return 0;\n        if (row == 0 && col == 0)\n            return 1;\n        if (row < 0 || col < 0)\n            return 0;     \n        int left = solve(row, col-1, obstacleGrid);  \n        int up = solve(row-1, col, obstacleGrid);  \n        return left + up;     \n    }    \npublic:\n    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {\n        int m = obstacleGrid.size(), n = obstacleGrid[0].size();\n        return solve(m-1, n-1, obstacleGrid);\n    }\n};\n```\n\n# Approach 2\nDP (Top Down Approach)\n\n# Complexity\n- Time complexity:\n$$O(m * n)$$\n\n- Space complexity:\n$$O(m * n)$$\n\n# Code\n```\nclass Solution {\nprivate:\n    int solve(int row, int col, vector<vector<int>>& obstacleGrid, vector<vector<int>>& dp) {\n        if (row >= 0 && col >= 0 && obstacleGrid[row][col] == 1)\n            return 0;\n        if (row == 0 && col == 0)\n            return 1;\n        if (row < 0 || col < 0)\n            return 0;   \n        if (dp[row][col] != -1)\n            return dp[row][col];      \n        int left = solve(row, col-1, obstacleGrid, dp);  \n        int up = solve(row-1, col, obstacleGrid, dp);  \n        return dp[row][col] = left + up;     \n    }    \npublic:\n    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {\n        int m = obstacleGrid.size(), n = obstacleGrid[0].size();\n        vector<vector<int>> dp(m, vector<int>(n, -1));\n        return solve(m-1, n-1, obstacleGrid, dp);\n    }\n};\n```\n\n# Approach 3\nDP (Bottom Up Approach)\n\n# Complexity\n- Time complexity:\n$$O(m * n)$$\n\n- Space complexity:\n$$O(m * n)$$\n\n# Code\n```\nclass Solution {    \npublic:\n    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {\n        int m = obstacleGrid.size(), n = obstacleGrid[0].size();\n        vector<vector<int>> dp(m, vector<int>(n, -1));\n        for (int i = 0; i < m; i++) {\n            for (int j = 0; j < n; j++) {\n                if (obstacleGrid[i][j] == 1) {\n                    dp[i][j] = 0;\n                    continue;\n                }\n                if (i == 0 && j == 0) {\n                    dp[i][j] = 1;\n                    continue;\n                }\n                int left = 0, up = 0;\n                if (j > 0)\n                    left = dp[i][j-1];\n                if (i > 0)\n                    up = dp[i-1][j];    \n                dp[i][j] = left + up;\n            }\n        }\n        return dp[m-1][n-1];\n    }\n};\n```\n\n# Approach 4\nDP (Bottom Up Approach) + Space Optimization\n\n# Complexity\n- Time complexity:\n$$O(m * n)$$ \n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```\nclass Solution { \npublic:\n    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {\n        int m = obstacleGrid.size(), n = obstacleGrid[0].size();\n        vector <int> prev(n, 0);\n        for (int i = 0; i < m; i++) {\n            vector <int> cur(n, 0);\n            for (int j = 0; j < n; j++) {\n                if (obstacleGrid[i][j] == 1) {\n                    cur[j] = 0;\n                    continue;\n                }\n                if (i == 0 && j == 0) {\n                    cur[j] = 1;\n                    continue;\n                }\n                int left = 0, up = 0;\n                if (j > 0)\n                    left = cur[j-1];\n                if (i > 0)\n                    up = prev[j];    \n                cur[j] = left + up;\n            }\n            prev = cur;\n        }\n        return prev[n-1];\n    }\n};\n```
['C++']