Find total number of unique paths in a grid with obstacles

Companies:
  • Amazon Interview Questions
  • Google Interview Questions
  • Microsoft Interview Questions

Problem Statement

A robot is located at the top-left corner of a m x n grid .

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid.

Now consider if some obstacles are added to the grids. How many unique paths would there be?

Sample Test Cases

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

Problem Solution

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

We will create a 2D matrix of the same size as the given matrix.

Next step will be to traverse the array row wise and fill the values in it.

So, if an obstacle is found we will assign that cell value of 0.

For the first row and column, set the value to 1 if obstacle is not found.

Set the sum of the left and the lower values if obstacle is not present at that corresponding position in the given matrix ie F(x, y) = F(x-1, y ) +F(x , y-1).

Return the last value of the created 2d matrix.

Complexity Analysis

Time Complexity: O(mn) Since we are traversing the entire matrix.

Space Complexity: O(mn) As we are creating a dp matrix of the same size as given in the problem.

Code Implementation

#include<bits/stdc++.h>
using namespace std;

#define m 3
#define n 4

int get_unique_paths_with_obstacle(int arr[m][n])
{
    int path [m] [n];

// Base condition
// initialize the array to 0
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<n;j++)
        {
            path[i][j]=0;
        }
    }
// Base condition
    if(arr[0][0] == 1) return 0;    //no paths if the starting place is itself an obstacle
    path[0][0] = 1; //initializing the first position

// set the first row
    for(int i=1;i<m;i++)
    {
        if(arr[i][0]==0)
        {
            path[i][0] = path[i-1][0];
        }
    }

// set the first column
    for(int i=1;i<n;i++)
    {
        if(arr[0][i]==0)
        {
            path[0][i] = path[0][i-1];
        }
    }


// apply the formula path[i][j] = path [i - 1][j] + path [i][j - 1] if input_array[i][j] != 1 and 0 otherwise.

    for (int i = 1; i < m; i++)
        for (int j = 1; j < n; j++)
            if (!arr[i][j])
                path[i][j] = path[i - 1][j] + path[i][j - 1];

            return path[m - 1][n - 1];
}

int main()
{
    int arr [m][n];

    for (int i = 0; i < m; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            // inserting obstacle
            if ( (i == 0 && j == 2) || (i == 1 && j == 0)||(i == 1 && j == 2))
            {
                arr[i] [j] = 1;
                continue;
            }

            arr[i] [j] = 0;
        }
    }

    cout<<"Input array is "<<endl;
    for (int i = 0; i < m; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            cout<< arr[i][j]<<" ";
        }
        cout<<endl;
    }

    int result = get_unique_paths_with_obstacle(arr);

    cout<<"The number of unique paths for a "<<m <<" x "<< n<<" matrix is = "<< result<<endl;

    return 0;
}

 

Scroll to Top