Unique paths ii

Array Dynamic Programming Matrix

44.2% acceptance

Jan 12, 2026

9636

559

You are given an m x n integer array grid. There is a robot initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time. An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle. Return the number of possible unique paths that the robot can take to reach the bottom-right corner. The testcases are generated so that the answer will be less than or equal to 2 * 109.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

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();
    
    if obstacle_grid[0][0] == 1 || obstacle_grid[m-1][n-1] == 1 {
      return 0;
    }
    
    let mut dp = vec![vec![0; n]; m];
    dp[0][0] = 1;
    
    // Initialize first column
    for i in 1..m {
      if obstacle_grid[i][0] == 0 && dp[i-1][0] == 1 {
        dp[i][0] = 1;
      }
    }
    
    // Initialize first row
    for j in 1..n {
      if obstacle_grid[0][j] == 0 && dp[0][j-1] == 1 {
        dp[0][j] = 1;
      }
    }
    
    // Fill the dp table
    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]
  }
}