Unique Paths II

medium dp grid

Problem

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

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];
}

Explanation

A robot walks from the top-left to the bottom-right of a grid, moving only right or down, but some cells are blocked. We count the distinct paths with a DP table where dp[i][j] = number of ways to reach cell (i, j).

The core rule is simple: you can only arrive at a cell from above or from the left, so dp[i][j] = dp[i-1][j] + dp[i][j-1]. The two boundary checks just treat off-grid neighbors as 0.

Obstacles are handled by forcing dp[i][j] = 0 on any blocked cell — no path can pass through it, so it contributes nothing to cells further down or right. If the start itself is blocked, the answer is immediately 0.

We seed dp[0][0] = 1 (one way to be at the start) and fill the grid row by row.

Example: [[0,0,0],[0,1,0],[0,0,0]]. The middle cell is blocked, so paths must route around it. Only 2 valid routes remain, which is dp[2][2].

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