Unique paths in a Grid with Obstacles

Given a grid of size m * n, let us assume you are starting at (1, 1) and your goal is to reach (m, n). At any instance, if you are on (x, y), you can either go to (x, y + 1) or (x + 1, y).
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and empty space are marked as 1 and 0 respectively in the grid.

Examples:  

Input: [[0, 0, 0],
        [0, 1, 0],
        [0, 0, 0]]
Output : 2
There is only one obstacle in the middle.

Method 1: Recursion

We have discussed the problem to count the number of unique paths in a Grid when no obstacle was present in the grid. But here the situation is quite different. While moving through the grid, we can get some obstacles that we can not jump and the way to reach the bottom right corner is blocked. 

2 

Time Complexity: O(2^m*n)
Auxiliary Space: O(m+n) , because worst path will be when we iterate along corner cells, Recursion will not have all the paths so Space can’t be O(n*m) it should be O(n+m)

Method 2: Using DP

1) Top-Down

The most efficient solution to this problem can be achieved using dynamic programming. Like every dynamic problem concept, we will not recompute the subproblems. A temporary 2D matrix will be constructed and value will be stored using the top-down approach. 

2 

Time Complexity: O(m*n) 
Auxiliary Space: O(m*n)

2) Bottom-Up

A temporary 2D matrix will be constructed and value will be stored using the bottom-up approach. 

Approach:

• Create a 2D matrix of the same size as the given matrix to store the results.
• Traverse through the created array row-wise and start filling the values in it.
• If an obstacle is found, set the value to 0.
• For the first row and column, set the value to 1 if an obstacle is not found.
• Set the sum of the right and the upper values if an obstacle is not present at that corresponding position in the given matrix
• Return the last value of the created 2d matrix

Below is the implementation of the above approach:

2 

Time Complexity: O(m*n) 
Auxiliary Space: O(m*n)

Method 3: Space Optimization of DP solution.

In this method, we will use the given ‘A’ 2D matrix to store the previous answer using the bottom-up approach.

Approach

• Start traversing through the given ‘A’ 2D matrix row-wise and fill the values in it.
• For the first row and the first column set the value to 1 if an obstacle is not found.
• For the first row and first column, if an obstacle is found then start filling 0 till the last index in that particular row or column.
• Now start traversing from the second row and column ( eg: A[ 1 ][ 1 ]).
• If an obstacle is found, set 0 at particular Grid ( eg: A[ i ][ j ] ), otherwise set sum of upper and left values at A[ i ][ j ].
• Return the last value of the 2D matrix.

Below is the implementation of the above approach. 

2

Time Complexity: O(m*n)  
Auxiliary Space: O(1)

The 2D Dp Approach:

As Per Problem tell us that we can move in two ways  can either go to (x, y + 1) or (x + 1, y). So we just calculate all possible outcome in both ways and store in 2d dp vector and return the dp[0][0] i.e all possible ways that takes you from (0,0) to (n-1,m-1);

2 

Time Complexity: O(M*N),For traversing all possible ways.
Auxiliary Space: O(M*N),For storing in 2D Dp Vector.