Complexity Analysis:

Time Complexity: O(M*N), where M is the number of row and N is the number of column in 2D array. As the whole matrix is traversed once using two nested loops.

Space Complexity:O(M*N), As an external DP Array of size ‘M*N’ is used to store the intermediate calculations.1f:T5538,

If we closely look at the relationship obltained in the tabulation approach, dp[i][j] = dp[i-1][j] + dp[i][j-1]), we see that we only need the previous row and column, in order to calculate dp[i][j]. Therefore we can space optimize it.

Initially, we can take a dummy row ( say prev) and initialize it as 0.

Now the current row(say temp) only needs the previous row value and the current row’s value in order to calculate dp[i][j].

At the next step, the 'temp' array becomes the 'prev' of the next step and using its values we can still calculate the next row’s values.

At last prev[n-1] will give us the required answer, as it will store the total answer in top-down approach.

Solution

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

class Solution {
private:
    // Function to solve the problem using tabulation
    int func(int m, int n, vector<vector<int>>& matrix) {
        
        vector<int> prev(n, 0), curr(n, 0);
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                
                // Base conditions
                if (matrix[i][j] == 1) {
                    /* If there's an obstacle at the 
                    cell, no paths can pass through it*