Unique Paths in JavaScript with Time Complexity Analysis

Input:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
Output: 2
Explanation:
There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

Understanding the Problem

The core challenge of this problem is to navigate a grid with obstacles, finding all possible paths from the top-left to the bottom-right corner. This problem is significant in robotics and pathfinding algorithms, often used in AI and game development. A common pitfall is not accounting for obstacles correctly, which can lead to incorrect path counts.

Approach

To solve this problem, we can use dynamic programming. The idea is to create a 2D array `dp` where `dp[i][j]` represents the number of unique paths to reach cell `(i, j)`. We initialize the starting point `dp[0][0]` to 1 if there is no obstacle there. For each cell, if it is not an obstacle, we sum the paths from the cell above and the cell to the left.

Naive Solution

A naive solution would involve recursively exploring all possible paths, but this approach is not optimal due to its exponential time complexity.

Optimized Solution

The optimized solution uses dynamic programming to store intermediate results, reducing the time complexity to O(n * m) and space complexity to O(n * m).

Algorithm

1. Create a 2D array `dp` of the same size as the grid, initialized to 0.
2. Set `dp[0][0]` to 1 if the starting cell is not an obstacle.
3. Iterate through each cell in the grid. For each cell `(i, j)`, if it is not an obstacle:
   • Add the value from the cell above (`dp[i-1][j]`) if it exists.
   • Add the value from the cell to the left (`dp[i][j-1]`) if it exists.
4. The value at `dp[n-1][m-1]` will be the number of unique paths to the bottom-right corner.

Code Implementation

/**
 * @param {number[][]} obstacleGrid
 * @return {number}
 */
function uniquePathsWithObstacles(obstacleGrid) {
    // Get the dimensions of the grid
    const n = obstacleGrid.length;
    const m = obstacleGrid[0].length;

    // Create a 2D dp array initialized to 0
    const dp = Array.from({ length: n }, () => Array(m).fill(0));

    // Initialize the starting point
    dp[0][0] = obstacleGrid[0][0] === 0 ? 1 : 0;

    // Fill the dp array
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (obstacleGrid[i][j] === 1) {
                dp[i][j] = 0; // No path through an obstacle
            } else {
                if (i > 0) dp[i][j] += dp[i-1][j]; // Add paths from above
                if (j > 0) dp[i][j] += dp[i][j-1]; // Add paths from the left
            }
        }
    }

    // The bottom-right corner contains the number of unique paths
    return dp[n-1][m-1];
}

Complexity Analysis

The time complexity of this solution is O(n * m) because we iterate through each cell in the grid once. The space complexity is also O(n * m) due to the additional 2D array used for dynamic programming.

Edge Cases

Potential edge cases include:

• The starting cell or the ending cell is an obstacle.
• All cells are obstacles.
• Single row or single column grids.

Testing

To test the solution comprehensively, consider the following test cases:

• Grids with no obstacles.
• Grids with obstacles blocking all paths.
• Grids with a single path due to obstacles.

Thinking and Problem-Solving Tips

When approaching such problems:

• Break down the problem into smaller subproblems.
• Consider edge cases and constraints early.
• Use dynamic programming to store intermediate results and avoid redundant calculations.

Conclusion

Understanding and solving the "Unique Paths" problem with obstacles is crucial for mastering dynamic programming and pathfinding algorithms. By breaking down the problem and using an optimized approach, we can efficiently find the number of unique paths in a grid with obstacles.

Additional Resources

For further reading and practice, consider the following resources:

• LeetCode: Unique Paths II
• GeeksforGeeks: Dynamic Programming
• Coursera: Algorithms Part I