Leetcode 2435. Paths in Matrix Whose Sum Is Divisible by K |Dynamic Programming| Weekly Contest Hard

[@probabilitycodingisfunis1]

int mod = 1e9+7; int numberOfPaths(vector& grid, int k) { vectordp(grid.size(), vector( grid[0].size(), vector(51,-1))); return fnc(grid, k, 0, 0, 0, dp); } int fnc(vector& grid, int k, int i,int j, int sum, vector&dp) { //base conditions if(i=grid[0].size()) { return 0; } //end cell of grid if(i==grid.size()-1 && j==grid[0].size()-1) { sum+=grid[i][j]; if(sum%k==0)return 1; return 0; } if(dp[i][j][sum%k]!=-1)return dp[i][j][sum%k]; long down = fnc(grid, k, i+1, j, sum+grid[i][j],dp); //down long right = fnc(grid, k, i, j+1, sum+grid[i][j], dp); //right return dp[i][j][sum%k] = (down%mod +right%mod)%mod; }

[@myitraju7996]

i m beginner,is it good to start my coding journey direct from leetcode?

[@yaswanthkosuru]

@@myitraju7996 yaa absolutely

[@myitraju7996]

@@yaswanthkosuru thanks 😊

[@asishmaity884]

are didi java se karwao plss

[@utkarsh_ishan]

Please don't stop making videos on leetcode contests. Your explanation for contests is by far the best I have ever seen

[@AbhishekKumar-qy1ek]

Thank you didi. Please make a video of third problem i.e using a robot to print the lexicographically Smallest string.

[@AbhishekSingh-l9i]

may god bless you and your channel

[@stupidbutcurious6206]

very well explained... i came across this question while searching for another similar question... can you please help solve.. The Question is:- Given an array of integers of size N, count all possible distinct triplets whose sum is exactly divisible by given integer K. for triplets i, j, k --> i

[@ankitpandey64]

if I don't understand from anywhere you always help me, always great explanation thank you

[@AyushKumar-rh1vy]

Great explanation, Thanks for your effort 🔥

[@barathnatarajan8566]

HEY sis, i got placed at a company for 10lpa base. thank u so much for ur DSA videos . It helped me a lot

[@probabilitycodingisfunis1]

Congratsss, all the best for your future!

[@reshmaparveen6679]

Great job di

[@millybrown5168]

why do we need to memoize the rem ?? i tried doing this using 2d dp but it didn't work. don't know where I'm going wrong int num(vector& grid, int &k,int i,int j,int sum,vector &dp){ if(i

[@probabilitycodingisfunis1]

@Mily, it will give wrong answer. consider the example [[1,2,3],[4,5,6],[7,8,9]] and k = 5, when you calculate for i=1,j=1 ,(grid[i][j]=5), for the path 1->2->5->8->9 gives sum=25 and sum%k==0 (because k=5), so you will store dp[i][j]=1 for this cell, so when you come to next function call in this cell at i=1,j=1 ,(grid[i][j]=5), for the path 1->2->5->6->9, the actual sum is 23, which means 23%5 !=0, but since you will not go to the complete path 1->2->5->6->9 using recursion, rather get your saved answer from dp[1][1] which tells you that it is 1 , you will stop there and consider answer to be 1 for this path also which is wrong, hence according to your code you will not get correct answer, you need to check for sum also ( new paths at each coordinate may have different sum than before which may not give answer)

[@millybrown5168]

@@probabilitycodingisfunis1 understood, thank you so much

[@abhinavverma4111]

Wonderful Explanation. Can you suggest a similar problem to 3D dp?

[@Idukhan-jj9kc]

Best solution Alisha 👌😉

[@midhileshmomidi3120]

Best solution

[@ayushsinghrathore360]

Ma'am plzz Reply.... Ma'am Aap all approaches btate ho And they are really good but for the popular question which tells us new approaches to aap uski approach khud se hi discover krte ho ya aapko bhi kayi baar dekhna hota h efficient approach.

[@ayushsinghrathore360]

For example if we are new and solve snake and ladder problem toh khud se pura sochna muskil hota h same goes with special or popular questions which needs some different and new approach.

[@ayushsinghrathore360]

Add a Reply plzz

[@rishav144]

@@ayushsinghrathore360 bro , new approach khud se sochne ka try kro...bcoz Interviewer will tell u to optimize time and space complexity ......Pehle regular approach se solve kro....phir new approach try kro ...try for 20-30 mins ....then u may refer editorials or video solns if unable to solve through new or optimized approaches

[@galibkiyaadein4627]

Koi khud se nhi sochta kuch bro to be honest sab standard practice kar karke. Yddd mar lete hai

[@omkarkadam309]

"annnd listening" in the end is hilarious

[@pujarisanthoshbabu4073]

Kudos to your hardwork

[@ROHITKADYANJI]

Maam continuosly getting rejected some times in tr ,hr, coding round how to handle this please help

[@amangaur4231]

You are best

[@rishav144]

pls dont stop uploading videos of leetcode questions😣

[@probabilitycodingisfunis1]

Will start soon again, thanks 👍

[@rishav144]

@@probabilitycodingisfunis1 thanks ...your Leetcode videos are really helpful

[@tejasahuja7133]

Nice solution, just one request to please increase frequency of your videos

[@AmanSharma-vb5jl]

I don't have words to describe, only i can say "waah waah Kamal kr diya dhoti ko faad kr rumal kr diya" You are seriously awesome.

[@shubamgoswami]

Fun fact 3rd one is harder than the 4th one waiting for 3 and welcome back 🥳

[@mayanksoni9046]

You are returning 1 and 0 while question is asking total number of paths. Can u explain How they are getting added please.

[@AbhishekPandey-yl3bp]

When you need the total count of something,you need to return 1 or 0 in the base case so it'll keep adding up to give the total count

[@rahulbhardwaj4380]

this was great question! thanks for the explanation! And please accept my request on linkedin 😅