Unique Paths in a Grid with Obstacles in Java

A "N*M" grid is provided to us. Some obstacles can be found in the grid. In the grid, if a cell has a value of -1 then it is a "blockage," while a value of 0 denotes a non-blockage. A blocked cell has no opening that may allow to pass.

The total number of distinct paths from the grid's upper-left corner to its lower-right corner must be counted. We can travel either downwards or to the right in every cell.

Example 1:

Input:

Output:

Explanation:

Here the number of unique paths present in the grid is 2 which are represented by arrows. As a result of being blocked, there is no way to get through cell [1][1], hence any alternative legal paths that do not go through it must be counted.

Approach: Using Recursion

Algorithm:

The steps listed below will be used to obtain a recursive solution:

Step -1: Construct a dp array of size [n][m].

Step -2: Every time we want to determine the result for a specific row and column (let's say F(i,j)), we first determine whether the result has already been determined using the dp array (i.e. dp[i][j]!= -1).

Step -3: If yes, just give back the result from the dp array.

Step -4: If not, then we will utilise the recursive relation as usual and, prior to exiting the function, we will set dp[i][j] to the answer we get. If this is the case, then we are finding the answer for the values we have provided for the first time.

Implementation:

FileName: UniquePaths1.java

import java.util.*;

import java.io.*;

public class UniquePaths1

{

    static int gridObstaclesUtil(int i, int j, int[][] grid, int[][] dp)

    {

      // if the current cell consists of an obstacle

      if(i>0 && j>0 && grid[i][j]==-1)

        return 0;

      // destination has reached and count the no of paths

      if(i==0 && j == 0)

        return 1;

      // crosssed the boundary of the matrix

      if(i<0 || j<0)

        return 0;

      // if there is no obstacle present in the cell

      if(dp[i][j]!=-1)

        return dp[i][j];

      // since top-down recursion is used

      // to go upwards, we will reduce i by 1, and

      //to move towards left we will reduce j by 1.

      int top = gridObstaclesUtil(i-1,j,grid,dp);

      int down = gridObstaclesUtil(i,j-1,grid,dp);

      return dp[i][j] = top + down;

    }

    static int gridObstacles(int n, int m, int[][] grid)

    {

        int dp[][]=new int[n][m];

        // for the rows with -1

        for(int row[]: dp)

            Arrays.fill(row,-1);

        return gridObstaclesUtil(n-1,m-1,grid,dp);

    }

    public static void main(String args[])

    {

      int[][] grid = { {0,0,0}, {0,-1,0}, {0,0,0}};

      int n = grid.length;

      int m = grid.length;

      System.out.println("The number of unique paths in a grid are: "+ gridObstacles(n,m,grid));

    }

}

Output:

The number of unique paths in a grid are: 2

Complexity Analysis:

The time complexity is O(N*M) as the maximum number of recursive calls will be N*M. The space complexity is O((M-1) + (N-1)) + O(N*M) where (M-1) + (N-1) is the path length and an external DP Array of size ‘N*M’.

Approach: Memoization of Space

If we analyse the relationship,

dp[i][j] = dp[i-1][j] + dp[i][j-1]

We can see that in order to calculate dp[i][j], all we require is the previous row and column. Consequently, we can space-optimize it.

Algorithm:

Step -1: To begin with, we can choose a dummy row (let's say prior) and initialise it to 0.

Step -2: Now, to calculate dp[i][j], all that is required for the current row (let's say, temp) is the value of the previous row and the value of the current row.

Step -3: The temp array changes from the previous step's prior to the subsequent step at the following step, and we can still determine the values for the following row using its values.

Step -4: At last, prev[n-1] will give us the required answer.

Implementation:

FileName: UniquePaths2.java

import java.util.*;

import java.io.*;

public class UniquePaths2

{

    static int gridObstacles(int n, int m,int[][] grid)

    {

        // dummy row is created

        int prev[]=new int[n];

        for(int i=0; i
        {

            // current row

            int temp[]=new int[m];

            for(int j=0; j
            {

                // current cell having an obstacle

                if(i>0 && j>0 && grid[i][j]==-1)

                {

                    temp[j]=0;

                    continue;

                }

                // reached the destination

                // count the number of paths

                if(i==0 && j==0)

                {

                    temp[j]=1;

                    continue;

                }

                // top-down approach is implemented

                int up=0;

                int left =0;

                if(i>0)

                    up = prev[j];

                if(j>0)

                    left = temp[j-1];

                temp[j] = up + left;

            }

            prev = temp;

        }

        return prev[n-1];

    }

    public static void main(String args[])

    {

        int[][] grid = { {0,0,0}, {0,-1,0}, {0,0,0}};

        int n = grid.length;

        int m = grid.length;

        System.out.println("The number of unique paths in a grid are: " + gridObstacles(n,m,grid));

    }

}

Output:

The number of unique paths in a grid are: 2

Complexity Analysis:

The time complexity is O(N*M) and the space complexity is O(N) where we are using an external array of size ‘N’ to store only one row.