✅ 100% Dynamic Programming [VIDEO] - Optimal Solution
Problem Understanding\n\nIn the "Unique Paths II" problem, we are presented with a grid filled with obstacles and open paths. Starting from the top-left corner,
# Problem Understanding\n\nIn the "Unique Paths II" problem, we are presented with a grid filled with obstacles and open paths. Starting from the top-left corner, the goal is to find the number of unique paths that lead to the bottom-right corner. We can only move right or down at any point in time. If a cell has an obstacle, we cannot pass through it.\n\nFor example, consider the following grid:\n\n$$\n\\begin{array}{ccc}\n0 & 0 & 0 \\\\\n0 & 1 & 0 \\\\\n0 & 0 & 0 \\\\\n\\end{array}\n$$\n\n![63_tsa.png](https://assets.leetcode.com/users/images/ec5e79ee-d2e3-47aa-adaf-aa07efa4b36b_1691802199.0146625.png)\n\n\n- The grid cells with obstacles are colored in red.\n- The two unique paths from the top-left to the bottom-right corner are represented by the blue and green dashed lines.\n\nFrom the plot, you can see the two possible routes:\n\n- The blue path goes Right -> Right -> Down -> Down.\n- The green path goes Down -> Down -> Right -> Right.\n\n---\n\n# Live Coding\nhttps://youtu.be/pJ40_FmXAfo\n\n- [in Python \uD83D\uDC0D](https://youtu.be/pJ40_FmXAfo)\n- [in Rust \uD83E\uDD80](https://youtu.be/xt_1OzCH_NA)\n\n# Approach\n\n## The Basic Idea\n\nThe underlying concept is rooted in dynamic programming. Essentially, for any cell `(i, j)`, the number of ways you can reach it is the sum of the ways you can reach the cell directly above it `(i-1, j)` and the cell directly to its left `(i, j-1)`. However, this is only true if the cell `(i, j)` does not have an obstacle. If it does, then the number of ways to reach this cell is 0 because it\'s inaccessible.\n\n### 2D Transition:\nIn a 2D dynamic programming approach, you would have a `dp` array of size `m x n`, where ` dp[i][j] ` represents the number of ways to reach cell ` (i, j) `.\n\nThe transition formula would be:\n$$ dp[i][j] = \n\\begin{cases} \n0 & \\text{if } obstacleGrid[i][j] = 1 \\\\\ndp[i-1][j] + dp[i][j-1] & \\text{otherwise}\n\\end{cases}\n$$\n\nSo, for each cell ` (i, j) `, if there\'s no obstacle, its value would be the sum of the cell above it and the cell to its left.\n\n### Translation to 1D:\n\nNow, given the 2D transition, notice how for any cell \\( (i, j) \\), we only need values from the current row and the previous row. This observation allows us to reduce our 2D `dp` array to two 1D arrays, `previous` and `current`.\n\nThe transition formula in 1D would be analogous to the 2D version but slightly adjusted:\n\nFor the first column (`j = 0`):\n$$ current[0] = \n\\begin{cases} \n0 & \\text{if } obstacleGrid[i][0] = 1 \\\\\nprevious[0] & \\text{otherwise}\n\\end{cases}\n$$\n\nFor other columns:\n$$ current[j] = \n\\begin{cases} \n0 & \\text{if } obstacleGrid[i][j] = 1 \\\\\nprevious[j] + current[j-1] & \\text{otherwise}\n\\end{cases}\n$$\n\nHere, `previous` is analogous to `dp[i-1]` and `current` is analogous to `dp[i]` from our 2D approach. After processing each row, we\'ll swap `previous` and `current` to roll over to the next iteration.\n\nThe transition remains conceptually the same between the 2D and 1D versions. The 1D optimization simply leverages the observation that for each cell, we only need data from the current and previous rows. This reduces space complexity from $$ O(m \\times n) $$ to $$ O(n) $$.\n\nThis rolling array technique is a common optimization strategy in dynamic programming problems involving grids.\n\n### Step-by-step Breakdown:\n\n1. **Initialization**:\n   - We initialize the `previous` array with zeros. This array represents the number of ways to reach each cell in the previous row.\n   - We set `previous[0]` to 1 because there\'s only one way to get to the starting cell (by starting there!).\n   \n2. **Iterate through the Grid**:\n   - For each row, we consider each cell:\n     - If the cell has an obstacle, it\'s unreachable, so the number of ways to get there (`current[j]`) is 0.\n     - Otherwise, the number of ways to reach the cell is the sum of the ways to reach the cell above and the cell to the left. This translates to `current[j-1] + previous[j]`.\n   - Once we\'ve processed a row, we set `previous` to `current`, preparing for the next iteration.\n\n3. **Result**:\n   - Once we\'ve processed all rows, `previous[n-1]` gives us the number of unique paths to the bottom-right corner of the grid.\n\n## Example\n\nUsing the earlier example:\n\n$$\n\\begin{array}{ccc}\n0 & 0 & 0 \\\\\n0 & 1 & 0 \\\\\n0 & 0 & 0 \\\\\n\\end{array}\n$$\n\nHere\'s how the `previous` and `current` arrays evolve:\n\nThe function\'s output matches the example description:\n\n**Initial State**:\n- `previous`: $$[1, 0, 0]$$\n- `current`: $$[0, 0, 0]$$\n\n**After processing row 0**:\n- `previous`: $$[1, 0, 0]$$\n- `current`: $$[1, 1, 1]$$\n\n**After processing row 1**:\n- `previous`: $$[1, 1, 1]$$\n- `current`: $$[1, 0, 1]$$\n\n**After processing row 2**:\n- `previous`: $$[1, 0, 1]$$\n- `current`: $$[1, 1, 2]$$\n\nFrom the final state of the `previous` array, we can infer that there are 2 unique paths from the top-left to the bottom-right corner, avoiding obstacles. This matches the expected result.\n\n# Complexity\n\n**Time Complexity:** $$O(m \\times n)$$\n**Space Complexity:** $$O(n)$$\n\nThis solution is optimal in terms of both time and space complexity. It efficiently computes the number of unique paths by building upon previous calculations.\n\n# Performance\n\n| Language    | Runtime (ms) | Runtime Beat (%) | Memory (MB) | Memory Beat (%) |\n|-------------|--------------|------------------|-------------|-----------------|\n| Go          | 0            | 100%             | 2.4         | 71.38%          |\n| C++         | 0            | 100%             | 7.6         | 81.25%          |\n| Java        | 0            | 100%             | 40.5        | 72.53%          |\n| Rust        | 1            | 85%              | 2           | 87.50%          |\n| Python3     | 38           | 99.30%           | 16.3        | 82.98%          |\n| JavaScript  | 47           | 97.40%           | 41.6        | 97.86%          |\n| C#          | 81           | 80.72%           | 38.7        | 63.25%          |\n\n![perf_518.png](https://assets.leetcode.com/users/images/3cb0ceab-f4d0-4cad-9711-d0e194aad604_1691801587.1220236.png)\n\n\n---\n\n# Code\n\n``` Python []\nclass Solution:\n    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:\n        if not obstacleGrid or not obstacleGrid[0] or obstacleGrid[0][0] == 1:\n            return 0\n        \n        m, n = len(obstacleGrid), len(obstacleGrid[0])\n        \n        previous = [0] * n\n        current = [0] * n\n        previous[0] = 1\n        \n        for i in range(m):\n            current[0] = 0 if obstacleGrid[i][0] == 1 else previous[0]\n            for j in range(1, n):\n                current[j] = 0 if obstacleGrid[i][j] == 1 else current[j-1] + previous[j]\n            previous[:] = current\n        \n        return previous[n-1]\n```\n``` C++ []\nclass Solution {\npublic:\n    int uniquePathsWithObstacles(std::vector<std::vector<int>>& obstacleGrid) {\n        if (obstacleGrid.empty() || obstacleGrid[0].empty() || obstacleGrid[0][0] == 1) {\n            return 0;\n        }\n        \n        int m = obstacleGrid.size();\n        int n = obstacleGrid[0].size();\n        \n        std::vector<int> previous(n, 0);\n        std::vector<int> current(n, 0);\n        previous[0] = 1;\n        \n        for (int i = 0; i < m; i++) {\n            current[0] = obstacleGrid[i][0] == 1 ? 0 : previous[0];\n            for (int j = 1; j < n; j++) {\n                current[j] = obstacleGrid[i][j] == 1 ? 0 : current[j-1] + previous[j];\n            }\n            previous = current;\n        }\n        \n        return previous[n-1];\n    }\n};\n```\n``` Go []\nfunc uniquePathsWithObstacles(obstacleGrid [][]int) int {\n    if len(obstacleGrid) == 0 || len(obstacleGrid[0]) == 0 || obstacleGrid[0][0] == 1 {\n        return 0\n    }\n\n    m := len(obstacleGrid)\n    n := len(obstacleGrid[0])\n\n    previous := make([]int, n)\n    current := make([]int, n)\n    previous[0] = 1\n\n    for i := 0; i < m; i++ {\n        if obstacleGrid[i][0] == 1 {\n            current[0] = 0\n        } else {\n            current[0] = previous[0]\n        }\n        \n        for j := 1; j < n; j++ {\n            if obstacleGrid[i][j] == 1 {\n                current[j] = 0\n            } else {\n                current[j] = current[j-1] + previous[j]\n            }\n        }\n        previous, current = current, previous\n    }\n    return previous[n-1]\n}\n```\n``` Rust []\nimpl Solution {\n    pub fn unique_paths_with_obstacles(obstacleGrid: Vec<Vec<i32>>) -> i32 {\n        if obstacleGrid.is_empty() || obstacleGrid[0].is_empty() || obstacleGrid[0][0] == 1 {\n            return 0;\n        }\n        \n        let m = obstacleGrid.len();\n        let n = obstacleGrid[0].len();\n        \n        let mut previous = vec![0; n];\n        let mut current = vec![0; n];\n        previous[0] = 1;\n        \n        for row in &obstacleGrid {\n            current[0] = if row[0] == 1 { 0 } else { previous[0] };\n            for j in 1..n {\n                if row[j] == 1 {\n                    current[j] = 0;\n                } else {\n                    current[j] = current[j-1] + previous[j];\n                }\n            }\n            std::mem::swap(&mut previous, &mut current);\n        }\n        \n        previous[n-1]\n    }\n}\n```\n``` Java []\npublic class Solution {\n    public int uniquePathsWithObstacles(int[][] obstacleGrid) {\n        if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0].length == 0 || obstacleGrid[0][0] == 1) {\n            return 0;\n        }\n\n        int m = obstacleGrid.length;\n        int n = obstacleGrid[0].length;\n\n        int[] previous = new int[n];\n        int[] current = new int[n];\n        previous[0] = 1;\n\n        for (int i = 0; i < m; i++) {\n            current[0] = obstacleGrid[i][0] == 1 ? 0 : previous[0];\n            for (int j = 1; j < n; j++) {\n                current[j] = obstacleGrid[i][j] == 1 ? 0 : current[j-1] + previous[j];\n            }\n            System.arraycopy(current, 0, previous, 0, n);\n        }\n\n        return previous[n-1];\n    }\n}\n```\n``` JavaScript []\n/**\n * @param {number[][]} obstacleGrid\n * @return {number}\n */\nvar uniquePathsWithObstacles = function(obstacleGrid) {\n    if (!obstacleGrid.length || !obstacleGrid[0].length || obstacleGrid[0][0] === 1) {\n        return 0;\n    }\n\n    let m = obstacleGrid.length;\n    let n = obstacleGrid[0].length;\n\n    let previous = new Array(n).fill(0);\n    let current = new Array(n).fill(0);\n    previous[0] = 1;\n\n    for (let i = 0; i < m; i++) {\n        current[0] = obstacleGrid[i][0] === 1 ? 0 : previous[0];\n        for (let j = 1; j < n; j++) {\n            current[j] = obstacleGrid[i][j] === 1 ? 0 : current[j-1] + previous[j];\n        }\n        previous = [...current];\n    }\n\n    return previous[n-1];\n};\n```\n``` C# []\npublic class Solution {\n    public int UniquePathsWithObstacles(int[][] obstacleGrid) {\n        if (obstacleGrid == null || obstacleGrid.Length == 0 || obstacleGrid[0].Length == 0 || obstacleGrid[0][0] == 1) {\n            return 0;\n        }\n\n        int m = obstacleGrid.Length;\n        int n = obstacleGrid[0].Length;\n\n        int[] previous = new int[n];\n        int[] current = new int[n];\n        previous[0] = 1;\n\n        for (int i = 0; i < m; i++) {\n            current[0] = obstacleGrid[i][0] == 1 ? 0 : previous[0];\n            for (int j = 1; j < n; j++) {\n                current[j] = obstacleGrid[i][j] == 1 ? 0 : current[j-1] + previous[j];\n            }\n            Array.Copy(current, previous, n);\n        }\n\n        return previous[n-1];\n    }\n}\n```\n\n# Conclusion\n\nThe "Unique Paths II" problem showcases how dynamic programming can help find solutions to combinatorial problems in a structured and efficient manner. By understanding the relationship between subproblems, we can incrementally build the solution and avoid redundant computations. \n\nAs with any algorithmic challenge, practice and understanding the underlying principles are key. Don\'t hesitate to tweak, optimize, and experiment with the solution to deepen your understanding!\n\n# Live Coding in Rust\nhttps://youtu.be/xt_1OzCH_NA
['Array', 'Dynamic Programming', 'C++', 'Java', 'Go', 'Python3', 'Rust', 'JavaScript', 'C#']