Longest Arithmetic Subsequence of Given Difference | Recur + Memo | Optimal | META | Leetcode-1218

[@floatingpoint7629]

thanks for the excellent explanation. i watched two videos before. none of them built the solution from recursion and jumped directly into the accepted solution

[@codestorywithMIK]

Thank you so much for the trust in my small channel. I believe is explaining things from ground. I hope it helps everyone 🙏🙏❤️❤️

[@itspravas]

@@codestorywithMIK did you mean "I believe **in** explaining things from ground." ... your friendly spell checker 🫡

[@iamnoob7593]

Just amazing explanation

[@vineetkumarmotwani474]

haven't watched the video yet. Was able to do it on my own, fairly easy for anyone if they have tried Arithmetic Subsequence 2 or watched that video from ur channel. 👍❤

[@codestorywithMIK]

❤️❤️❤️

[@dayashankarlakhotia4943]

Good explanation with dryrun

[@codestorywithMIK]

Thank you Daya 🙏👍🏻

[@shabananoor9423]

Best best explanation

[@anuppatankar4294]

Great Video 🤩

[@codestorywithMIK]

Thank you Anup 😇

[@sauravbiswajit8091]

Great explanation 😊

[@codestorywithMIK]

Thank you Saurav ❤️🙏

[@vineettanwar7880]

thank you sir

[@codestorywithMIK]

Thank you for watching 🙏❤️😇

[@shaikfayaz4750]

Good explanation.

[@codestorywithMIK]

Thank you 😇❤️

[@dikshantyadav1110]

nice explanation , please keep up the good work, Commended

[@codestorywithMIK]

Thanks a lot 😇❤️

[@prathampahad9788]

Thank you sir Done today's challenge

[@Rajat_maurya]

O(n) not expected, i thought it will get more optimized by tabular but...😅

[@codestorywithMIK]

Hi Rajat, Sorry, but can you explain. I didn’t get you 🥹🙏

[@Rajat_maurya]

@@codestorywithMIK no question, it was a surprised gesture.

[@satyasanjay1339]

excellent explanation.

[@codestorywithMIK]

Thank you so much Satya ❤️🙏

[@itspravas]

32:10 app ne explanation ke baad hi code likh liya hoga... indeed, the solution clicked in a single sentence between 24:25 & 24:40. I went, submitted the code, then came back to complete the video. 🤗

[@codestorywithMIK]

Woww. Thanks a lot 😇❤️

[@doomhead9109]

AAA => As Always Awesome

[@codestorywithMIK]

Thank you 🙏❤️😇

[@AtulBhadouriya-m8s]

can anyone explain me why we can,t use take skip concept here,,we are also using the same concept of take,skip in LIS but there that algo works,,,if we are skipping some parts then what,s the issue with that...overall we got the path which contain that subsequence that has all integers that are required for max length...@MIKE

[@swayamterode4965]

Note @ 1:53 the subsequence will be 7 , 5, 3 ,1 not 7, 5, 3!

[@codestorywithMIK]

Thanks a lot ❤️❤️

[@souravjoshi2293]

Such a detailed explanation bhai. Thanks a lot. Got to learn a lot from this video

[@ugcwithaddi]

Masterpiece explanation. Thanks for the recursion one 🙌🙌

[@turing_machine544]

I also tried the recursion + memo but it could only pass 34 test cases. I am able to write recursive codes ,because of you. I am always going to appreciate your teaching. Here is my code, that i wrote: int solve(int i, vector& arr, int diff, int n, vector&dp){ if(i >= n){ return 0; } if(dp[i] != -1){ return dp[i]; } int steps = 1; for(int j = i+1; j < n; j++){ if(arr[j]-arr[i] == diff){ steps = 1 + solve(j, arr, diff, n, dp); } } return dp[i] = steps; } int longestSubsequence(vector& arr, int diff) { int n = arr.size(); int ans = 0; vectordp(n+1, -1); for(int i = 0; i < n; i++){ ans = max(ans, solve(i, arr, diff, n, dp)); } return ans; }

[@codestorywithMIK]

I am so glad you tried recursive and memo first. Thank you for sharing 🙏❤️

[@Rajdweep]

broo the most optimal solution was so unintuitive xd, i kept trying with recur+memo bt couldn't get past n square

[@codestorywithMIK]

Actually the optimal solution is the better version of “Longest Increasing Subsequence Bottom Up” The only slight variation is that we need to take care of common difference. I will try to make things clear better in my future videos. Thank you so much for your feedback

[@Rajdweep]

@@codestorywithMIK yaa that qs is another op qs bro it even had a bs solution, ur explanation was very clear bro bt tht solution is not something that would come fast while looking at the qs for the first time, same as the bs approach for LIS

[@codestorywithMIK]

Totally agree. Thanks a lot ❤️

[@Rajdweep]

@@codestorywithMIK ur welcome bro

[@AlishaKhan-ww3io]

You are a gem 💎. Thanks a lot for detailed explanations and dry run

[@utkarshguruji8894]

Rather than saying ki kitni subsequence ka part hai we can say ki map[previous value] is the number of subsequences ending with previous value.

[@yashsinghal7471]

1 4 5 3 4 5 6 in this example, if I don't skip 4, 5 then I can't get 3, 4, 5, 6.. so we also have to take care of skip..???

[@codestorywithMIK]

Actually that is actually taken care of. We are trying to start from every index. Suppose you start from index 0, Then it will start from 1 and then further moving you won’t get any element with common difference = 1 Now, you try with index = 1, i.e. 4 Now you move further and try to see if you get 5 (because 5-4 = 1) And you get it at index 2. Now from index 2, you want to find further next element 6 (because 6-5 = 1) and you get it in the end So you get - {4, 5, 6} ---- Now you try with index = 2, i.e. 5 , which will help you to find subsequence - {5,6} --- And so on you reach index = 3 i.e. 3 And moving ahead you get subsequence - {3,4,5,6} which is a better one of length 4

[@shanayagupta4002]

Sir, suppose we were able to code the recursive with memoization approach in the interview so is this sufficient to satisfy the interviewer ? or we must be able to tell the DP approach?

[@codestorywithMIK]

Actually Recursion + memo is equally good. However, it totally depends on the company, interviewer. But if you have already clearly explained the recursion + memo then it will leave a good impression. However if there are other candidates who were able to solve bottom up or optimal solution, might get an edge for selection

[@shanayagupta4002]

​@@codestorywithMIK noted 📝sir, thank you sir.

[@codeandtalk6]

❤

[@anuragjain8674]

Hello Sir Sir Aap competitive programming bhi karte hein kya If yes, thoda guide kar dijiye please

[@codestorywithMIK]

Hello Anurag, I have not done much of competitive programming but i think the first step will always be to strengthen the concepts of each data structure which are targeted in competitive programming. I believe my concepts playlist might help in the that. Also GfG has a good curated list of guide

[@priyadarshanghoshhazra7648]

Can anyone help why is this code giving wrong answer fortest case:[4,12,10,0,-2,7,-8,9,-9,-12,-12,8,8] difference=0. Expected output:2 Output:3 Recursive Code: class Solution { private int f(int []arr,int diff,int i) { if(i==arr.length-1) { return 1; } int ans=0; int temp=0; for(int j=i+1;j

[@mileshsoni5016]

int solve (vector& arr, int start, int n, int difference){ int answer = 0; for(int i=start; i

[@shibu4513]

class Solution { public: int n ; int solve(vector& arr,int i , int d,int p) { if(i == n) return 0; int take = 0 ,skip = 0; if(p == 0 || arr[i] - p == d) { take = 1 + solve(arr,i+1,d,arr[i]) ; } skip = solve(arr,i+1,d,p); return max(take,skip) ; } int longestSubsequence(vector& arr, int d) { n = arr.size() ; int p = 0 ; return solve(arr,0,d,p) ; } }; why this one is not working ??

[@RahulRaj-kx6cd]

❤

[@codestorywithMIK]

Thank you Rahul ❤️🙏