Unique paths in a Grid with Obstacles-Using Space Optimised DP

Using Space Optimised DP – O(m*n) Time and O(n) Space

We can maximize space by utilizing a single 1D array dp of size c (number of columns), since every dp[i][j] depends just on the left cell of the current row and the previous row.

• Whereas dp[j – 1] adds pathways from the left cell of the current row, dp[j] holds the cumulative paths up to the current cell in the preceding row.
• Dp[c-1] will provide the overall unique paths to reach the bottom-right corner of the grid once all rows have been handled.

C++

// C++ code to find unique paths with obstacles 
// using space optimization
#include <bits/stdc++.h>
using namespace std;

int uniquePathsWithObstacles(vector<vector<int>>& grid) {
    int r = grid.size(), c = grid[0].size();

    // Initialize DP array with zeros
    vector<int> dp(c, 0);

    // Set the starting cell if there's no obstacle
    dp[0] = (grid[0][0] == 0) ? 1 : 0;

    // Fill the DP array for each row
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
          
            // If there's an obstacle, set dp[j] to 0
            if (grid[i][j] == 1) {
                dp[j] = 0;
            } else if (j > 0) {
              
                // Add the value from the left cell
                dp[j] += dp[j - 1];
            }
        }
    }

    // Return paths count for the bottom-right cell
    return dp[c - 1];
}

int main() {
  
    vector<vector<int>> grid = { { 0, 0, 0 },
                                 { 0, 1, 0 },
                                 { 0, 0, 0 } };
  
    cout << uniquePathsWithObstacles(grid);
}

Java

// Java code to find unique paths with obstacles 
// using space optimization
class GfG {

    static int uniquePathsWithObstacles(int[][] grid) {
        int r = grid.length, c = grid[0].length;

        // Initialize DP array with zeros
        int[] dp = new int[c];
        
        // Set the starting cell if there's no obstacle
        dp[0] = (grid[0][0] == 0) ? 1 : 0;

        // Fill the DP array for each row
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
              
                // If there's an obstacle, 
                  // set dp[j] to 0
                if (grid[i][j] == 1) {
                    dp[j] = 0;
                } else if (j > 0) {
                  
                    // Add the value from the left cell
                    dp[j] += dp[j - 1];
                }
            }
        }

        // Return paths count for the 
          // bottom-right cell
        return dp[c - 1];
    }

    public static void main(String[] args) {
      
        int[][] grid = { { 0, 0, 0 },
                         { 0, 1, 0 },
                         { 0, 0, 0 } };

        System.out.println(uniquePathsWithObstacles(grid));
    }
}

Python

# Python code to find unique paths with 
# obstacles using space optimization

def uniquePathsWithObstacles(grid):
    r, c = len(grid), len(grid[0])

    # Initialize DP array with zeros
    dp = [0] * c

    # Set the starting cell if there's
    # no obstacle
    dp[0] = 1 if grid[0][0] == 0 else 0

    # Fill the DP array for each row
    for i in range(r):
        for j in range(c):
          
            # If there's an obstacle, 
            # set dp[j] to 0
            if grid[i][j] == 1:
                dp[j] = 0
            elif j > 0:
              
                # Add the value from the
                # left cell
                dp[j] += dp[j - 1]

    # Return paths count for the 
    # bottom-right cell
    return dp[c - 1]

if __name__ == "__main__":
  
    grid = [[0, 0, 0],
            [0, 1, 0],
            [0, 0, 0]]

    print(uniquePathsWithObstacles(grid))

C#

// C# Code to find unique paths with obstacles
// using tabulation
using System;

class GfG {

    public static int uniquePathsWithObstacles(int[,] grid) {
        int r = grid.GetLength(0), c = grid.GetLength(1);
        
        // Initialize DP table with zeros
        int[,] dp = new int[r, c];

        // Initialize starting cell if there's no
          // obstacle
        if(grid[0, 0] == 0) {
            dp[0, 0] = 1;
        }

        // Fill the DP table
        for(int i = 0; i < r; i++) {
            for(int j = 0; j < c; j++) {
              
                // If cell has an obstacle, set 
                  // paths to 0
                if(grid[i, j] == 1) {
                  dp[i, j] = 0;
                } 
                else {
                  
                    // Accumulate paths from top cell
                    if(i > 0) dp[i, j] += dp[i-1, j];
                  
                    // Accumulate paths from left cell
                    if(j > 0) dp[i, j] += dp[i, j-1];
                }
            }
        }

        // Return paths count for the
          // bottom-right cell
        return dp[r-1, c-1];
    }

    static void Main() {
      
        int[,] grid = { { 0, 0, 0 },
                        { 0, 1, 0 },
                        { 0, 0, 0 } };
      
        Console.WriteLine(uniquePathsWithObstacles(grid));
    }
}

JavaScript

// Javascript code to find unique paths with
// obstacles using tabulation
function uniquePathsWithObstacles(grid) {

    let r = grid.length, c = grid[0].length;

    // Initialize DP table with zeros
    let dp
        = Array.from({length : r}, () => Array(c).fill(0));

    // Initialize starting cell if there's 
    // no obstacle
    if (grid[0][0] === 0) {
        dp[0][0] = 1;
    }

    // Fill the DP table
    for (let i = 0; i < r; i++) {
        for (let j = 0; j < c; j++) {

            // If cell has an obstacle, set 
            // paths to 0
            if (grid[i][j] === 1) {
                dp[i][j] = 0;
            }
            else {

                // Accumulate paths from top cell
                if (i > 0)
                    dp[i][j] += dp[i - 1][j];

                // Accumulate paths from left cell
                if (j > 0)
                    dp[i][j] += dp[i][j - 1];
            }
        }
    }

    // Return paths count for the
    // bottom-right cell
    return dp[r - 1][c - 1];
}

const grid = [ [ 0, 0, 0 ], [ 0, 1, 0 ], [ 0, 0, 0 ] ];
console.log(uniquePathsWithObstacles(grid));