🦀🐍🐹 Fast DP in Rust + Go + Python
Intuition \uD83E\uDD14\nWhen faced with the "Unique Paths II" problem, the first thought that might come to mind is to navigate through the grid cell by cell. H
# Intuition \uD83E\uDD14\nWhen faced with the "Unique Paths II" problem, the first thought that might come to mind is to navigate through the grid cell by cell. However, with obstacles in our path, a simple traversal won\'t cut it. We need to remember our past (paths) and make informed decisions as we move. The good news? Dynamic programming is here to save the day (and our robot)!\n\n---\n\n# Approach \uD83D\uDE80\nUsing dynamic programming, we keep track of the number of ways to reach each cell. The number of paths to a cell is the sum of the paths from the cell above and the cell on the left. However, if there\'s an obstacle, that cell is a no-go zone (0 paths). \n\nTo keep our memory usage in check, we use two 1D arrays, `previous` and `current`, instead of a 2D matrix. As we traverse each row, we update the `current` array and then move on to the next row, making `current` our `previous` and starting fresh.\n\nThis rolling array technique is efficient and does the job without hogging memory.\n\n---\n\n# Complexity \uD83E\uDDEE\n- **Time complexity:** $$O(m \\times n)$$ \n  - We traverse through each cell of the grid once, where \\(m\\) is the number of rows and \\(n\\) is the number of columns.\n\n- **Space complexity:** $$O(n)$$\n  - We use two 1D arrays to keep track of our paths, irrespective of the grid\'s size.\n\n---\n\n# Code \uD83E\uDD80\n```rust []\nimpl Solution {\n    pub fn unique_paths_with_obstacles(obstacleGrid: Vec<Vec<i32>>) -> i32 {\n        // Basic checks\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        // Initialize our trusty path trackers\n        let mut previous = vec![0; n];\n        let mut current = vec![0; n];\n        previous[0] = 1;\n        \n        // Traverse each row in the grid\n        for row in &obstacleGrid {\n            // Set the starting cell for the row\n            current[0] = if row[0] == 1 { 0 } else { previous[0] };\n            for j in 1..n {\n                // If there\'s an obstacle, it\'s a dead end\n                if row[j] == 1 {\n                    current[j] = 0;\n                } else {\n                    // Otherwise, the paths are the sum from above and left\n                    current[j] = current[j-1] + previous[j];\n                }\n            }\n            // Roll the arrays for the next row\n            std::mem::swap(&mut previous, &mut current);\n        }\n        \n        // Our answer lies in the bottom-right corner\n        previous[n-1]\n    }\n}\n```\n``` Go []\nfunc uniquePathsWithObstacles(obstacleGrid [][]int) int {\n    // Handle edge cases: empty grid or start cell has an obstacle\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    // Initialize two 1D arrays to keep track of the number of paths\n    previous := make([]int, n)\n    current := make([]int, n)\n    \n    // The top-left corner has only one way to be reached (start point)\n    previous[0] = 1\n\n    // Loop through each row of the grid\n    for i := 0; i < m; i++ {\n        // If there\'s an obstacle at the beginning of the row, no way to get there\n        // Otherwise, it inherits the path count from the previous row\n        if obstacleGrid[i][0] == 1 {\n            current[0] = 0\n        } else {\n            current[0] = previous[0]\n        }\n        \n        // Loop through the remaining cells in the current row\n        for j := 1; j < n; j++ {\n            // If there\'s an obstacle, no paths to this cell\n            if obstacleGrid[i][j] == 1 {\n                current[j] = 0\n            } else {\n                // Number of paths is the sum of paths from the top and the left\n                current[j] = current[j-1] + previous[j]\n            }\n        }\n        \n        // Swap current and previous arrays for the next iteration\n        previous, current = current, previous\n    }\n    \n    // Return the number of paths to the bottom-right corner\n    return previous[n-1]\n}\n\n```\n``` Python []\nclass Solution:\n    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:\n        # Handle edge cases: empty grid or start cell has an obstacle\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        # Initialize two 1D arrays to keep track of the number of paths\n        previous = [0] * n\n        current = [0] * n\n        \n        # The top-left corner has only one way to be reached (start point)\n        previous[0] = 1\n        \n        # Loop through each row of the grid\n        for i in range(m):\n            # If there\'s an obstacle at the beginning of the row, no way to get there\n            # Otherwise, it inherits the path count from the previous row\n            current[0] = 0 if obstacleGrid[i][0] == 1 else previous[0]\n            \n            # Loop through the remaining cells in the current row\n            for j in range(1, n):\n                # If there\'s an obstacle, no paths to this cell\n                if obstacleGrid[i][j] == 1:\n                    current[j] = 0\n                else:\n                    # Number of paths is the sum of paths from the top and the left\n                    current[j] = current[j-1] + previous[j]\n            \n            # Update previous array for the next iteration\n            previous[:] = current\n        \n        # Return the number of paths to the bottom-right corner\n        return previous[n-1]\n\n```\n---\n\n**Final Thoughts:** With dynamic programming and our crabby companion \uD83E\uDD80, we\'ve efficiently solved this intriguing grid problem. Embrace the power of Rust and keep exploring! If you ever feel lost in a grid full of obstacles, just remember: every step you take is building towards the solution. Happy coding! \uD83D\uDE80
['Array', 'Dynamic Programming', 'Go', 'Python3', 'Rust']