1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
/**
 * Calculate the number of unique paths from top-left to bottom-right corner with obstacles.
 * Dynamic Programming (2D) approach.
 *
 * @param {number[][]} obstacleGrid - Grid with obstacles (1) and empty spaces (0)
 * @return {number} - Number of unique paths
 */
function uniquePathsWithObstacles(obstacleGrid) {
  const m = obstacleGrid.length;
  const n = obstacleGrid[0].length;
 
  // Initialize DP array
  const dp = Array(m).fill().map(() => Array(n).fill(0));
 
  // Set base case for starting cell
  dp[0][0] = obstacleGrid[0][0] === 0 ? 1 : 0;
 
  // If starting cell is an obstacle, there are no paths
  if (dp[0][0] === 0) {
    return 0;
  }
 
  // Set base cases for first row
  for (let j = 1; j < n; j++) {
    dp[0][j] = obstacleGrid[0][j] === 0 ? dp[0][j - 1] : 0;
  }
 
  // Set base cases for first column
  for (let i = 1; i < m; i++) {
    dp[i][0] = obstacleGrid[i][0] === 0 ? dp[i - 1][0] : 0;
  }
 
  // Fill DP array
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = obstacleGrid[i][j] === 0 ? dp[i - 1][j] + dp[i][j - 1] : 0;
    }
  }
 
  return dp[m - 1][n - 1];
}
 
/**
 * Calculate the number of unique paths from top-left to bottom-right corner with obstacles.
 * Dynamic Programming (1D) approach.
 *
 * @param {number[][]} obstacleGrid - Grid with obstacles (1) and empty spaces (0)
 * @return {number} - Number of unique paths
 */
function uniquePathsWithObstaclesOptimized(obstacleGrid) {
  const m = obstacleGrid.length;
  const n = obstacleGrid[0].length;
 
  // Initialize DP array
  const dp = Array(n).fill(0);
 
  // Set base case for starting cell
  dp[0] = obstacleGrid[0][0] === 0 ? 1 : 0;
 
  // Set base cases for first row
  for (let j = 1; j < n; j++) {
    dp[j] = obstacleGrid[0][j] === 0 ? dp[j - 1] : 0;
  }
 
  // Fill DP array
  for (let i = 1; i < m; i++) {
    // Update first column
    if (obstacleGrid[i][0] === 1) {
      dp[0] = 0;
    }
 
    // Update rest of the row
    for (let j = 1; j < n; j++) {
      dp[j] = obstacleGrid[i][j] === 0 ? dp[j] + dp[j - 1] : 0;
    }
  }
 
  return dp[n - 1];
}
 
/**
 * Calculate the number of unique paths from top-left to bottom-right corner with obstacles.
 * In-place Dynamic Programming approach.
 *
 * @param {number[][]} obstacleGrid - Grid with obstacles (1) and empty spaces (0)
 * @return {number} - Number of unique paths
 */
function uniquePathsWithObstaclesInPlace(obstacleGrid) {
  const m = obstacleGrid.length;
  const n = obstacleGrid[0].length;
 
  // Create a copy of the grid to avoid modifying the input
  const grid = obstacleGrid.map(row => [...row]);
 
  // Set base case for starting cell
  grid[0][0] = grid[0][0] === 0 ? 1 : 0;
 
  // Set base cases for first row
  for (let j = 1; j < n; j++) {
    grid[0][j] = grid[0][j] === 0 ? grid[0][j - 1] : 0;
  }
 
  // Set base cases for first column
  for (let i = 1; i < m; i++) {
    grid[i][0] = grid[i][0] === 0 ? grid[i - 1][0] : 0;
  }
 
  // Fill grid
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      grid[i][j] = grid[i][j] === 0 ? grid[i - 1][j] + grid[i][j - 1] : 0;
    }
  }
 
  return grid[m - 1][n - 1];
}
 
// Test cases
const obstacleGrid1 = [
  [0, 0, 0],
  [0, 1, 0],
  [0, 0, 0]
];
console.log(uniquePathsWithObstacles(obstacleGrid1));  // 2
console.log(uniquePathsWithObstaclesOptimized(obstacleGrid1));  // 2
console.log(uniquePathsWithObstaclesInPlace(obstacleGrid1));  // 2
 
const obstacleGrid2 = [
  [0, 1],
  [0, 0]
];
console.log(uniquePathsWithObstacles(obstacleGrid2));  // 1
console.log(uniquePathsWithObstaclesOptimized(obstacleGrid2));  // 1
console.log(uniquePathsWithObstaclesInPlace(obstacleGrid2));  // 1
 
const obstacleGrid3 = [
  [1, 0]
];
console.log(uniquePathsWithObstacles(obstacleGrid3));  // 0
console.log(uniquePathsWithObstaclesOptimized(obstacleGrid3));  // 0
console.log(uniquePathsWithObstaclesInPlace(obstacleGrid3));  // 0