Unique Paths With Obstacles

medium dp grid

Problem

You have an m × n grid where 0 marks an open cell and 1 marks a blocked cell. Starting from the top-left and moving only right or down, return the number of distinct paths to the bottom-right.

Inputgrid = [[0,0,0],[0,1,0],[0,0,0]]

Output2

dp[i][j] = 0 on a blocked cell; otherwise dp[i][j] = dp[i−1][j] + dp[i][j−1]. dp[0][0] = 1 unless that cell is blocked.

grid (rows separated by ;)

def unique_paths_with_obstacles(grid):
    m, n = len(grid), len(grid[0])
    if grid[0][0] == 1: return 0
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = 1
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1: dp[i][j] = 0
            elif i == 0 and j == 0: continue
            else:
                dp[i][j] = (dp[i-1][j] if i > 0 else 0) + (dp[i][j-1] if j > 0 else 0)
    return dp[m-1][n-1]

function uniquePathsWithObstacles(grid) {
  const m = grid.length, n = grid[0].length;
  if (grid[0][0]) return 0;
  const dp = Array.from({ length: m }, () => new Array(n).fill(0));
  dp[0][0] = 1;
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j]) dp[i][j] = 0;
      else if (i || j) dp[i][j] = (i > 0 ? dp[i-1][j] : 0) + (j > 0 ? dp[i][j-1] : 0);
    }
  }
  return dp[m-1][n-1];
}

class Solution {
    public int uniquePathsWithObstacles(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        if (grid[0][0] == 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 (grid[i][j] == 1) dp[i][j] = 0;
                else if (i > 0 || j > 0)
                    dp[i][j] = (i > 0 ? dp[i-1][j] : 0) + (j > 0 ? dp[i][j-1] : 0);
            }
        }
        return dp[m-1][n-1];
    }
}

int uniquePathsWithObstacles(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    if (grid[0][0]) return 0;
    vector<vector<int>> dp(m, vector<int>(n, 0));
    dp[0][0] = 1;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j]) dp[i][j] = 0;
            else if (i || j)
                dp[i][j] = (i > 0 ? dp[i-1][j] : 0) + (j > 0 ? dp[i][j-1] : 0);
        }
    }
    return dp[m-1][n-1];
}

Time: O(m·n) Space: O(m·n)