Unique Paths in C++ with Time Complexity Analysis

A robot is located at the top-left corner of a n x m grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any moment of time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

Now consider obstacles are placed in some of the grid's cells. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

Note: n and m will be at most 100.

It is guaranteed that the answer can be represented as a 32-bit integer.

Example 1:

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 find the number of unique paths from the top-left corner to the bottom-right corner of a grid, considering that some cells may contain obstacles. The robot can only move right or down, which limits the possible paths.

This problem is significant in various applications such as robotics navigation, game development, and pathfinding algorithms. 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).

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

We can optimize the solution using dynamic programming:

Initialize a 2D array dp with the same dimensions as the grid.
If the starting cell or the ending cell has an obstacle, return 0 immediately.
Set dp[0][0] to 1 if there is no obstacle at the starting cell.
Iterate through the grid and update the dp array based on the values from the top and left cells, considering obstacles.

Algorithm

Here is a step-by-step breakdown of the dynamic programming approach:

Create a 2D array dp of the same size as the grid.
Initialize dp[0][0] to 1 if grid[0][0] is 0 (no obstacle).
Iterate through each cell in the grid:

If the cell contains an obstacle, set dp[i][j] to 0.
Otherwise, set dp[i][j] to the sum of dp[i-1][j] and dp[i][j-1], considering boundary conditions.

Return dp[n-1][m-1] as the result.

Code Implementation

#include <vector>
using namespace std;

// Function to calculate unique paths in a grid with obstacles
int uniquePathsWithObstacles(vector<vector<int>>& grid) {
    int n = grid.size();
    int m = grid[0].size();
    
    // If the starting or ending cell has an obstacle, return 0
    if (grid[0][0] == 1 || grid[n-1][m-1] == 1) {
        return 0;
    }
    
    // Create a 2D dp array initialized to 0
    vector<vector<int>> dp(n, vector<int>(m, 0));
    
    // Initialize the starting cell
    dp[0][0] = 1;
    
    // Fill the dp array
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (grid[i][j] == 1) {
                dp[i][j] = 0; // No path through an obstacle
            } else {
                if (i > 0) {
                    dp[i][j] += dp[i-1][j]; // Paths from the top
                }
                if (j > 0) {
                    dp[i][j] += dp[i][j-1]; // Paths from the left
                }
            }
        }
    }
    
    // Return the number of unique paths to the bottom-right corner
    return dp[n-1][m-1];
}

Complexity Analysis

The time complexity of this approach 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 dp.

Edge Cases

Consider the following edge cases:

The starting cell or the ending cell has an obstacle.
The grid is entirely filled with obstacles.
The grid has no obstacles.

Each of these cases should be tested to ensure the algorithm handles them correctly.

Testing

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

A grid with no obstacles.
A grid with obstacles blocking all paths.
A grid with a single row or column.
A large grid with random obstacles.

Using a testing framework like Google Test can help automate and manage these test cases effectively.

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

Break down the problem into smaller subproblems.
Think about the base cases and how to build the solution incrementally.
Use diagrams to visualize the problem and potential solutions.
Practice similar problems to improve your problem-solving skills.

Conclusion

In this blog post, we discussed the problem of finding unique paths in a grid with obstacles. We explored a dynamic programming approach to solve the problem efficiently and provided a detailed explanation of the algorithm and its implementation in C++. Understanding and solving such problems is crucial for developing strong problem-solving skills and preparing for technical interviews.

Additional Resources

For further reading and practice, consider the following resources: