Unique Paths Ii

                                            
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        
        vector<vector<long long>> dp(m, vector<long long>(n, 0));
        
        dp[0][0] = obstacleGrid[0][0] == 0 ? 1 : 0;
        
        for (int i = 1; i < m; i++) {
            dp[i][0] = obstacleGrid[i][0] == 0 ? dp[i - 1][0] : 0;
        }
        
        for (int j = 1; j < n; j++) {
            dp[0][j] = obstacleGrid[0][j] == 0 ? dp[0][j - 1] : 0;
        }
        
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 0) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        
        return dp[m - 1][n - 1];
    }
};

                                            
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;

        if (obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1) {
            return 0;
        }

        int[][] dp = new int[m][n];
        dp[0][0] = 1;

        for (int i = 1; i < m; i++) {
            dp[i][0] = obstacleGrid[i][0] == 1 ? 0 : dp[i-1][0];
        }

        for (int j = 1; j < n; j++) {
            dp[0][j] = obstacleGrid[0][j] == 1 ? 0 : dp[0][j-1];
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = obstacleGrid[i][j] == 1 ? 0 : dp[i-1][j] + dp[i][j-1];
            }
        }

        return dp[m-1][n-1];
    }
}

                                            
class Solution(object):
    def uniquePathsWithObstacles(self, obstacleGrid):
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        
        if obstacleGrid[0][0] == 1:
            return 0
        
        obstacleGrid[0][0] = 1
        
        for i in range(1, m):
            obstacleGrid[i][0] = int(obstacleGrid[i][0] == 0 and obstacleGrid[i - 1][0] == 1)
        
        for j in range(1, n):
            obstacleGrid[0][j] = int(obstacleGrid[0][j] == 0 and obstacleGrid[0][j - 1] == 1)
        
        for i in range(1, m):
            for j in range(1, n):
                if obstacleGrid[i][j] == 0:
                    obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1]
                else:
                    obstacleGrid[i][j] = 0
        
        return obstacleGrid[-1][-1]

                                            
int uniquePathsWithObstacles(int** obstacleGrid, int obstacleGridSize, int* obstacleGridColSize) {
    int m = obstacleGridSize;
    int n = obstacleGridColSize[0];
    
    int dp[m][n];
    memset(dp, 0, sizeof(dp));
    
    for(int i = 0; i < m; i++){
        if(obstacleGrid[i][0] == 1) break;
        dp[i][0] = 1;
    }
    
    for(int i = 0; i < n; i++){
        if(obstacleGrid[0][i] == 1) break;
        dp[0][i] = 1;
    }
    
    for(int i = 1; i < m; i++){
        for(int j = 1; j < n; j++){
            if(obstacleGrid[i][j] == 1) continue;
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    
    return dp[m-1][n-1];
}

                                            
public class Solution {
    public int UniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.Length;
        int n = obstacleGrid[0].Length;
        
        if (obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1) {
            return 0;
        }
        
        int[,] dp = new int[m, n];
        dp[0, 0] = 1;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    dp[i, j] = 0;
                } else {
                    if (i > 0) {
                        dp[i, j] += dp[i-1, j];
                    }
                    if (j > 0) {
                        dp[i, j] += dp[i, j-1];
                    }
                }
            }
        }
        
        return dp[m-1, n-1];
    }
}

                                            
/**
 * @param {number[][]} obstacleGrid
 * @return {number}
 */
var uniquePathsWithObstacles = function(obstacleGrid) {
    const m = obstacleGrid.length;
    const n = obstacleGrid[0].length;
    
    if (obstacleGrid[0][0] === 1 || obstacleGrid[m - 1][n - 1] === 1) {
        return 0;
    }
    
    obstacleGrid[0][0] = 1;
    
    for (let i = 1; i < m; i++) {
        obstacleGrid[i][0] = (obstacleGrid[i][0] === 0 && obstacleGrid[i - 1][0] === 1) ? 1 : 0;
    }
    
    for (let j = 1; j < n; j++) {
        obstacleGrid[0][j] = (obstacleGrid[0][j] === 0 && obstacleGrid[0][j - 1] === 1) ? 1 : 0;
    }
    
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            if (obstacleGrid[i][j] === 0) {
                obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
            } else {
                obstacleGrid[i][j] = 0;
            }
        }
    }
    
    return obstacleGrid[m - 1][n - 1];
};

                                            
function uniquePathsWithObstacles(obstacleGrid: number[][]): number {
    const m = obstacleGrid.length;
    const n = obstacleGrid[0].length;
    
    if (obstacleGrid[0][0] === 1) {
        return 0;
    }
    
    obstacleGrid[0][0] = 1;
    
    for (let i = 1; i < m; i++) {
        obstacleGrid[i][0] = obstacleGrid[i][0] === 0 && obstacleGrid[i - 1][0] === 1 ? 1 : 0;
    }
    
    for (let j = 1; j < n; j++) {
        obstacleGrid[0][j] = obstacleGrid[0][j] === 0 && obstacleGrid[0][j - 1] === 1 ? 1 : 0;
    }
    
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            if (obstacleGrid[i][j] === 0) {
                obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
            } else {
                obstacleGrid[i][j] = 0;
            }
        }
    }
    
    return obstacleGrid[m - 1][n - 1];
};

                                            
class Solution {
    /**
     * @param Integer[][] $obstacleGrid
     * @return Integer
     */
    function uniquePathsWithObstacles($obstacleGrid) {
        $m = count($obstacleGrid);
        $n = count($obstacleGrid[0]);
        
        $dp = array_fill(0, $m, array_fill(0, $n, 0));
        
        for ($i = 0; $i < $m; $i++) {
            for ($j = 0; $j < $n; $j++) {
                if ($obstacleGrid[$i][$j] == 1) {
                    $dp[$i][$j] = 0;
                } else {
                    if ($i == 0 && $j == 0) {
                        $dp[$i][$j] = 1;
                    } else {
                        $fromLeft = $j - 1 >= 0 ? $dp[$i][$j - 1] : 0;
                        $fromUp = $i - 1 >= 0 ? $dp[$i - 1][$j] : 0;
                        $dp[$i][$j] = $fromLeft + $fromUp;
                    }
                }
            }
        }
        
        return $dp[$m - 1][$n - 1];
    }
}

                                            
class Solution {
    func uniquePathsWithObstacles(_ obstacleGrid: [[Int]]) -> Int {
        let m = obstacleGrid.count
        let n = obstacleGrid[0].count
        
        var dp = Array(repeating: Array(repeating: 0, count: n), count: m)
        
        for i in 0..<m {
            for j in 0..<n {
                if obstacleGrid[i][j] == 1 {
                    dp[i][j] = 0
                } else if i == 0 && j == 0 {
                    dp[i][j] = 1
                } else if i == 0 {
                    dp[i][j] = dp[i][j - 1]
                } else if j == 0 {
                    dp[i][j] = dp[i - 1][j]
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
                }
            }
        }
        
        return dp[m - 1][n - 1]
    }
}

                                            
class Solution {
    fun uniquePathsWithObstacles(obstacleGrid: Array<IntArray>): Int {
        val m = obstacleGrid.size
        val n = obstacleGrid[0].size
        val dp = Array(m) { IntArray(n) }

        if (obstacleGrid[0][0] == 1) {
            return 0
        }

        dp[0][0] = 1

        for (i in 1 until m) {
            dp[i][0] = if (obstacleGrid[i][0] == 1) 0 else dp[i - 1][0]
        }

        for (j in 1 until n) {
            dp[0][j] = if (obstacleGrid[0][j] == 1) 0 else dp[0][j - 1]
        }

        for (i in 1 until m) {
            for (j in 1 until n) {
                dp[i][j] = if (obstacleGrid[i][j] == 1) 0 else dp[i - 1][j] + dp[i][j - 1]
            }
        }

        return dp[m - 1][n - 1]
    }
}

                                            
class Solution {
  int uniquePathsWithObstacles(List<List<int>> obstacleGrid) {
    int m = obstacleGrid.length;
    int n = obstacleGrid[0].length;
    
    List<List<int>> dp = List.generate(m, (index) => List.filled(n, 0));
    
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        if (obstacleGrid[i][j] == 1) {
          dp[i][j] = 0;
        } else if (i == 0 && j == 0) {
          dp[i][j] = 1;
        } else if (i == 0) {
          dp[i][j] = dp[i][j - 1];
        } else if (j == 0) {
          dp[i][j] = dp[i - 1][j];
        } else {
          dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
      }
    }
    
    return dp[m - 1][n - 1];
  }
}

                                            
func uniquePathsWithObstacles(obstacleGrid [][]int) int {
    m := len(obstacleGrid)
    n := len(obstacleGrid[0])

    dp := make([][]int, m)
    for i := range dp {
        dp[i] = make([]int, n)
    }

    for i := 0; i < m && obstacleGrid[i][0] == 0; i++ {
        dp[i][0] = 1
    }

    for j := 0; j < n && obstacleGrid[0][j] == 0; j++ {
        dp[0][j] = 1
    }

    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            if obstacleGrid[i][j] == 0 {
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
            }
        }
    }

    return dp[m-1][n-1]
}

                                            
# @param {Integer[][]} obstacle_grid
# @return {Integer}
def unique_paths_with_obstacles(obstacle_grid)
    m = obstacle_grid.length
    n = obstacle_grid[0].length
    
    dp = Array.new(m) { Array.new(n, 0) }
    
    (0...m).each do |i|
        break if obstacle_grid[i][0] == 1
        dp[i][0] = 1
    end
    
    (0...n).each do |j|
        break if obstacle_grid[0][j] == 1
        dp[0][j] = 1
    end
    
    (1...m).each do |i|
        (1...n).each do |j|
            dp[i][j] = obstacle_grid[i][j] == 1 ? 0 : dp[i - 1][j] + dp[i][j - 1]
        end
    end
    
    return dp[m - 1][n - 1]
end

                                            
object Solution {
    def uniquePathsWithObstacles(obstacleGrid: Array[Array[Int]]): Int = {
        val m = obstacleGrid.length
        val n = obstacleGrid(0).length
        val dp = Array.ofDim[Int](m, n)
        
        if (obstacleGrid(0)(0) == 1) return 0
        
        dp(0)(0) = 1
        
        for (i <- 0 until m) {
            for (j <- 0 until n) {
                if (obstacleGrid(i)(j) == 1) {
                    dp(i)(j) = 0
                } else {
                    if (i > 0) dp(i)(j) += dp(i - 1)(j)
                    if (j > 0) dp(i)(j) += dp(i)(j - 1)
                }
            }
        }
        
        dp(m - 1)(n - 1)
    }
}

                                            
impl Solution {
    pub fn unique_paths_with_obstacles(obstacle_grid: Vec<Vec<i32>>) -> i32 {
        let m = obstacle_grid.len();
        let n = obstacle_grid[0].len();
        
        let mut dp = vec![vec![0; n]; m];
        
        for i in 0..m {
            if obstacle_grid[i][0] == 1 {
                break;
            } else {
                dp[i][0] = 1;
            }
        }
        
        for j in 0..n {
            if obstacle_grid[0][j] == 1 {
                break;
            } else {
                dp[0][j] = 1;
            }
        }
        
        for i in 1..m {
            for j in 1..n {
                if obstacle_grid[i][j] == 0 {
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }
        
        dp[m-1][n-1]
    }
}

To solve this coding challenge

We can use dynamic programming to effectively navigate through the grid, considering both the obstacles and the available paths. The key idea is to dynamically update each cell in the grid to reflect the number of ways to reach it from the top-left corner (0, 0).

# Explanation

Initialization :

First, determine the dimensions of the grid \(m \times n\). If the starting cell \((0, 0)\) contains an obstacle (i.e.,
grid[0][0] == 1

), the robot cannot move, and thus, the number of unique paths is 0.

Setting Up the Starting Cell :

Initialize the starting cell. If there's no obstacle at the start, set
grid[0][0] = 1

because there is exactly one way to be at the starting point, which is to start there.

Handling the First Column :

For the first column, iterate through all rows. Any cell in the first column can only be reached from the cell directly above it. If a cell is not an obstacle and the cell above it also has a path, mark it as reachable by setting it to 1.

Handling the First Row :

Similarly, iterate through all columns in the first row. Any cell in the first row can only be reached from the cell directly to its left. If a cell is not an obstacle and the cell to its left also has a path, mark it as reachable by setting it to 1.

Filling the Rest of the Grid :

For each cell in the rest of the grid, calculate the number of unique paths to that cell by adding the number of paths from the cell directly above and the cell directly to the left, but only if the current cell is not an obstacle. If it is an obstacle, set the number of paths to 0.

Result :

The answer will be the value in the bottom-right corner \((m-1, n-1)\) of the grid, which indicates the number of unique paths to reach this cell from the top-left corner while avoiding obstacles.

Detailed Steps in Pseudocode

Initialize dimensions of the grid.
If the starting cell is an obstacle, return 0.
Set the starting cell's paths count to 1.
Update the path count for all cells in the first row.
Update the path count for all cells in the first column.
Iterate through all other cells in the grid and update their path counts based on paths from the left and top cells if they are not obstacles.
Return the path count at the bottom-right cell.

Detailed Pseudocode

                                            
# Step 1: Initialization
num_rows = number of rows in grid
num_columns = number of columns in grid

# Step 2: Check if the start cell (top-left) is an obstacle
if grid[0][0] == 1:
    return 0  # No possible paths if start is blocked

# Step 3: Initialize the start cell
grid[0][0] = 1  # There's one way to be at the start

# Step 4: Process first column
for row in range(1, num_rows):
    if grid[row][0] == 0 and grid[row - 1][0] == 1:
        grid[row][0] = 1
    else:
        grid[row][0] = 0  # There's an obstacle or no path from above

# Step 5: Process first row
for column in range(1, num_columns):
    if grid[0][column] == 0 and grid[0][column - 1] == 1:
        grid[0][column] = 1
    else:
        grid[0][column] = 0  # There's an obstacle or no path from the left
        
# Step 6: Process remaining grid cells
for row in range(1, num_rows):
    for column in range(1, num_columns):
        if grid[row][column] == 0:  # No obstacle at this cell
            grid[row][column] = grid[row - 1][column] + grid[row][column - 1]
        else:
            grid[row][column] = 0  # This cell is an obstacle

# Step 7: Return the result from bottom-right corner
return grid[num_rows - 1][num_columns - 1]

This pseudocode effectively sets up a dynamic programming approach to count the unique paths while considering the obstacles in the grid. By updating each cell based on possible paths from its neighboring cells (either from the left or above), we ensure that all valid paths are considered. The final result, found in the bottom-right cell, accurately represents the number of unique paths to the destination.