Number of Increasing Paths in a Grid | DFS + Memo | ADOBE, MICROSOFT | Leetcode-2328 | Live Code

This is the 38th Video on our Dynamic Programming (DP) Playlist.
In this video we will try to solve a very good DP Problem "Number of Increasing Paths in a Grid" (Leetcode - 2328)

Trust me, this will no longer be a Hard Problem. I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.

We will do live coding after explanation and see if we are able to pass all the test cases.

Problem Name : Number of Increasing Paths in a Grid
Company Tags : ADOBE, MICROSOFT

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝

#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview #interviewtips
#interviewpreparation #interview_ds_algo #hinglish

[procontent]

Leetcode is on fire giving only hard questions, but so does mik, so we need not worry😊. Big thanks as always very much appreciated🙏

[wearevacationuncoverers]

Never seen this extent of Hard work for video creation.

[codestorywithMIK]

Hi all,
If you guys want to do it in reverse manner, i.e. start from small to increasing large values, then just change the check :
from, < to >.
Code below :

class Solution {
public:

int m, n;
vector<vector<int>> directions = {
{-1, 0},
{0, -1}, {0, 1},
{1, 0}
};

long long MOD = 1e9+7;

bool isSafe(int i, int j) {
return (i < m && i >= 0 && j < n && j >= 0);
}

int t[1001][1001];

int dfs(vector<vector<int>>& grid, int i, int j) {


if(t[i][j] != -1)
return t[i][j];

int answer = 1; //grid[i][j] khud me increasing path to hai hi

for(auto &dir : directions) {

int i_ = i + dir[0];
int j_ = j + dir[1];

if(isSafe(i_, j_) && grid[i_][j_] > grid[i][j]) {

answer = (answer + dfs(grid, i_, j_)) % MOD;

}

}

return t[i][j] = answer;

}

int grid) {
m = grid.size();
n = grid[0].size();

memset(t, -1, sizeof(t));

int result = 0;

for(int i = 0; i < m; i++) {

for(int j = 0; j<n; j++) {

result = (result + dfs(grid, i, j)) % MOD;

}

}

return result;
}
};

[anuppatankar]

After watching the explanation I code it myself 👌🏻

[rajkrishanmahajan]

1st Time i am able to solve this question by my self thanku sir for Proper Dp Concept explanation

[sdmfslkdm]

Can you please find the mistake in this one
1) i used a visited array to avoid repeatation
2) i think i should use a for loop to do the code for each starting position
Q? other than that is the logic of my code correct ?

class Solution {
public:
int dp(vector<vector<int>>& grid, int r, int c, int r1, int c1, vector<vector<bool>>& visited, int prev) {
if (r >= r1 || c >= c1 || r < 0 || c < 0) {
return 0;
}
int a = 0, b = 0, c2 = 0, d = 0, e = 0;
if (!visited[r][c]) {
visited[r][c] = true;
if (grid[r][c ] > prev || prev == -1) {
a = dp(grid, r, c + 1, r1, c1, visited, grid[r][c ]);
}
if (c >= 0 && (grid[r][c ] > prev || prev == -1)) {
b = dp(grid, r, c - 1, r1, c1, visited, grid[r][c ]);
}
if (grid[r ][c] > prev || prev == -1) {
c2 = dp(grid, r + 1, c, r1, c1, visited, grid[r ][c]);
}
if (r >= 0 && (grid[r][c] > prev || prev == -1)) {
d = dp(grid, r - 1, c, r1, c1, visited, grid[r][c]);
}
visited[r][c] = false;
}
return 1 + (a + b + c2 + d) %
}

int grid) {
int r1 = grid.size();
int c1 = grid[0].size();
int totalPaths = 0 ;
for (int i = 0; i < r1; i++) {
for (int j = 0; j < c1; j++) {
vector<vector<bool>> visited(r1+1, vector<bool>(c1+1, false));
totalPaths += dp(grid, i, j, r1, c1, visited, -1);
totalPaths %=
}
}
return totalPaths;
}
};

[souravjoshi]

No one can teach like this magician. HARD qn seems like a baby task after your explanation

[faizan_moosa]

Ma'ashallah Bhai, Your Explanations are Super Awesome
Love from Hyderabad.

[fighter]

after understanding this question i solved leetcode problem number 329 by own thank you bhaiya 🥰

[RadecX]

Can you make videos on hard problems which come in weekly contests? It would be of tremendous help. And great video as always.

[Raj]

Ty for explanation solved this question in reverse manner by starting with start and finding how many increasing paths starting from that cell .
i also use issafe condition implicity and stored a prev element iff curr <= prev then ignore that path
code for the implementation is :-

int mod = 1e9+7;

int dfs(vector<vector<int>> &matrix, int i, int j, int parent, vector<vector<int>> &dp){

//implicit is safe condition
if(i>=matrix.size() || j>=matrix[0].size() || i<0 || j<0 || matrix[i][j]<=parent){
return 0;
}

if(dp[i][j]!=-1){ //memoization
return dp[i][j];
}

int down=dfs(matrix, i+1, j, matrix[i][j], dp);
int up=dfs(matrix, i-1, j, matrix[i][j], dp);
int right=dfs(matrix, i, j+1, matrix[i][j], dp);
int left=dfs(matrix, i, j-1, matrix[i][j], dp);


return dp[i][j]= 1 + (left + right + up + down)%mod; //1 khud ka hoga baki left right up down add krlo



}




int matrix) {



int n=matrix.size();
int m=matrix[0].size();

vector<vector<int>> dp(n, vector<int>(m, -1));


int count = 0;

for(int i=0;i<n;i++){
for(int j=0;j<m;j++){

count = (count + dfs(matrix, i, j, -1, dp))%mod; //initial prev / parent -1 dal denge sbse chota
}
}



return count;



}
};

[Raj]

I solved both the question this one and leetcode no 329 with very ease Tysm

[FreeAll-rblz]

Can you also so the bfs approach - using kahn's algo as well..?

[shadabkalim]

can you please take up the problem diameter of nary tree from leetcode? (its a ques only availalbe on subscription but availalbe elsewhere)

[password]

Very nicely explained as always...thanks sir!
Thanks for taking in yesterday's i/p and explaining as to how to approach the problems!!!
Can you also maybe make solutions to the medium and hard problems of weekly and biweekly contests...that would be great!
I found today's weekly contest's 3rd and 4th question very similar to DP but couldn't solve🥲

Once again, thanks a lot for your efforts making solutions to these tough problems and making them easier for us!

[alphadrones]

such an awesome solution.. and one request ...can you start covering online assessment solutions like 1 OA in 1 week.. it will be of great help

[U-nw]

bhaiya how can we write tabulation for this problem

[atmanirbharofficialindiaon]

Hey can you take the egg dropping problem next please? I can't find an understandable and simple code like yours for that problem so please do

[darshandesale]

sir please hume apki sikhani ki bohot jarrat he scratch se hum interested he apse sikhne ke liye please reply me (Course bhi chalega)

[ezcoding]

confused ...how ans is calculating at each dfs call