JB TAK FODEGA NHI .... TB TK CHODEGA NHI .... (MAANG)

DPL8 Grid Unique Paths I

In this Problem, we will solve the most asked coding interview problem: Grid Unique Paths I
Given two values M and N, which represent a matrix[M][N]. We need to find the total unique paths from the top-left cell (matrix[0][0]) to the rightmost cell (matrix[M-1][N-1]). At any cell we are allowed to move in only two directions:- bottom and right.

As we have to count all possible ways to go from matrix[0,0] to matrix[m-1,n-1], we can try recursion to generate all possible paths.

Recursice Approch

Steps to form the recursive solution
Step 1: Express the problem in terms of indexes: (i->row,j->coll)

We are given two variables M and N, representing the dimensions of a 2D matrix. For every different problem, this M and N will change.
We can define the function with two parameters i and j, where i and j represent the row and column of the matrix.

f(i,j) will give us a sub-answer for the region (marked in blue) below:

We will be doing a top-down recursion, i.e we will move from the cell[M-1][N-1] and try to find our way to the cell[0][0]. Therefore at every index, we will try to move up and towards the left.

Our Base Case is

When i=0 and j=0, that is we have reached the destination so we can count the current path that is going on, hence we return 1.

When i < 0 and j < 0, it means that we have crossed the boundary of the matrix and we couldn’t find a right path, hence we return 0.

The Recursive Function is

Step 2: Try all the choices to reach the goal. & Try out all possible choices at a given index.

As we are writing a top-down recursion, at every index we have two choices, one to go up(↑) and the other to go left(←). To go upwards, we will reduce i by 1, and move towards left we will reduce j by 1.

Step 3: Take the maximum of all the choices

AAs we have to count all the possible unique paths, we will return the sum of the choices(up and left) The final pseudocode after steps 1, 2, and 3:

Recursion Base Conditions

When i=0 and j=0, that is we have reached the destination so we can count the current path that is going on, hence we return 1.

When i < 0 and j < 0, it means that we have crossed the boundary of the matrix and we couldn’t find a right path, hence we return 0.

Recursion Tree

Time & Space Complexity

Time Complexity: O(2^N)
Reason: Exponential Time we find out the all the Possible Path
Space Complexity: O(N)
Reason: We are using a recursion stack space(O(N))

Memoization Approch

If we observe in the recursion tree, we will observe a many number of overlapping subproblems. Therefore the recursive solution can be memoized for to reduce the time complexity.

Steps to convert Recursive code to memoization solution:

Create a dp array of size [m][n] Inilisized with the -1

Whenever we want to find the answer of particular parameters (say fun(day,last)), we first check whether the answer is already calculated using the dp array(i.e dp[day][last]!= -1 ). If yes, simply return the value from the dp array. dp[day][last]

If not, then we are finding the answer for the given values for the first time, we will use the recursive relation as usual but before returning from the function, we will set dp[i][j] to the solution we get.

Time & Space Complexity

Time Complexity:O(N*M)
Reason: At max, there will be M*N calls of recursion..
Space Complexity: O((N-1)+(M-1)) + O(M*N)
Reason:We are using a recursion stack space: O((N-1)+(M-1)), here (N-1)+(M-1) is the path length and an external DP Array of size ‘M*N’.

Tabulation Approch

Tabulation is a ‘bottom-up’ approach where we start from the base case and reach the final answer that we want and Memoization is the Top-down Approch.

Steps to convert Recursive Solution to Tabulation one.

Declare a dp[] array of size [n][m]

First initialize the base condition values, i.e dp[0][0] = 1

Convert the Recurance Relation in the Term of the Index(i,j)

Our answer should get stored in dp[m-1][n-1]. We want to move from (0,0) to (m-1,n-1). But we can’t move arbitrarily, we should move such that at a particular i and j, we have all the values required to compute dp[i][j].

We have already filled the top-left corner (i=0 and j=0), if we move in any of the two following ways(given below), at every cell we do have all the previous values required to compute its value..

We can use two nested loops to have this traversal -> (row,coll)

At every cell we calculate up and left as we had done in the recursive solution and then assign the cell’s value as (up+left)

Note: For the first row and first column (except for the top-left cell), then up and left values will be zero respectively.

Time & Space Complexity

Time Complexity: O(M*N)
Reason:There are 2 nested loops
Space Complexity: O(N*M)
Reason: We are using an external array of size ‘M*N’’.

Space Optimization

If we closelly Observed if any Tabulation Approch we used the Some Limited Stuff like: dp[i][j] = dp[i-1][j] + dp[i][j-1] for the finding the our ans then definetly here Spaced Optimization is Possible in that types of Problems. Always Remember

Golden Rule

If we required only Prev row and Prev Collom then definetly we can Space Optimized

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(dp) 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.

Time & Space Complexity

Time Complexity:O(M*N)
Reason: There are three 2 nested loops
Space Complexity: O(N)
Reason: We are using an external array of size ‘N’ to store only one row.