Hii bhaiya mein ne aapse dp padhna start kiya and ab mein questions solve karr paa rha hu. I am very happy actually starting mein question samajh nahi aaya to aapke video se question samajh liya and then mein recursion+ memorization try kiya and vo completely execute hogya and jab mein ne aapka solution dekha to same to same code nikla. Thank you so much bhaiya for this wonderful explanation. Mein bohot saare jaano ke videos dekhta hu but aapka solution kafi informative lagta hai kyuki aap WHY pe kafi focus karte ho and meri saari curiosities aap clear kar dete ho. Thank you so much bhaiya for this wonderful video solutions it helps me a lot to solve the questions. Mein ne striver and Aditya verma ke saare videos dekhe and samajh bhi pura aaya but feel nahi aati thi and questions bhi solve nahi hote the but aapke case mein aisa nahi hai questions mein solve karr paa rha hu
int od= days[index]+1; int lb= lower_bound(begin(days),end(days),od)-begin(days); int f1= costs[0]+ f(lb, days, costs);
int sevenday= days[index]+7; int lb2= lower_bound(begin(days),end(days),sevenday)-begin(days); int f2= costs[1]+f(lb2, days, costs);
int thirtydays= days[index]+30; int lb3= lower_bound(begin(days),end(days),thirtydays)-begin(days); int f3= costs[2]+f(lb3, days, costs);
return dp[index]= min({f1,f2,f3}); } int mincostTickets(vector& days, vector& costs) { memset(dp, -1, sizeof(dp)); return f(0, days, costs); } }; My approach using lower_bound instead of looping in the function call. Runtime: 0 ms, faster than 100.00% of C++ online submissions for Minimum Cost For Tickets.
I just saw till 8:27 timestamp, bcz you made the problem statement simplified , i solved the rest of it on my own ! LC DESCRIPTION IS little confusing ,....thanks you deserve best!
If it is in my hand i would have made ur subscribers 20million + u deserve it .......i was a huge fan of striver i thought no one could make questions this much easier other than striver but then i saw one of ur video by chance and from then i forgot striver i just need everu topic to br covered by uuu ...u r just awesome sir.....
that t[max()] method just made me so excited and motivated to learn more, its like that OMG moment I used to have when I leant about a lot of new stuff in Engineering physics. One day expecting to reach that level of smartness to make neat and beautiful code.
How you can make so perfect recursion tree ,,, even after watching ur whole videos i tried to make trree by myself ,,, i forgot small things like what is index what will come inside node and blah blahh .... You are genius :)
I was able to do it by my own today, but came here to see if we can do it using just three variables because current value only depends on previous1, previous7 , previous30. I did it using 1d dp
Hi there, Actually this is a problem playlist and contains only questions. There is a separate playlist for dp concepts where it’s organised topic wise. I usually create two playlists for every topic : 1) Concepts Playlist - Contains from basic concepts to expert concepts. 2) Popular Interview Problems playlist. I have created concepts and interview problems playlist for 1) Graph 2) Recursion 3) DP 4) Segment Tree Planning soon to create concepts playlist for Tree as well. Graph Concepts - th-cam.com/play/PLpIkg8OmuX-LZB9jYzbbZchk277H5CbdY.html&si=lZG2IJTmSW4kRrx- Graph Popular Interview Problems - th-cam.com/play/PLpIkg8OmuX-I_49pdy1XFY6OcATnxUrrO.html&si=CG2JvGWVmvoSqvWA Recursion Concepts - th-cam.com/play/PLpIkg8OmuX-IBcXsfITH5ql0Lqci1MYPM.html&si=614iI4NyHY-FTeJH Recursion Problems (In progress) - th-cam.com/play/PLpIkg8OmuX-IXOgDP_YYiJFqfCFKFBDkO.html&si=88fBhRnr62OYTnDP DP Concepts (In progress) - th-cam.com/play/PLpIkg8OmuX-JhFpkhgrAwZRtukO0SkwAt.html&si=laFVYy6ep2BkOg0s DP Popular interview problems - th-cam.com/play/PLpIkg8OmuX-L_QqcKB5abYynQbonaNcq3.html&si=VHEn9b-wqTnAVyyi Segment Tree Concepts - th-cam.com/play/PLpIkg8OmuX-K1qUIQToCllUO0UIKXt8dB.html&si=xm7DqRN4H0eZwna4
I have on doubt in bottom up approach. for example we suppose days[]={1,4,6,7,8,15,20,38,44,45} now you said if i am on 45 then i must came from 15th , 38th or 44th day via 30 days, 7 days or 1 day pass respectively. But suppose if i came at 45th day by using a 30 day pass when i was at 20th day(6th index) then where is this case is handled i mean in those three cases which you have tought we are reaching reaching at destination when we were exactly before 1 day or 7 days or 30 days but what about this case. Can you please explain
Generals the coding is not often asked in system design because system design is more of a discussion interview about ideas and different approaches. And more Interview system design videos are coming soon on intermediate playlist
Because if you notice you need try for 7 days pass from i And 30 days pass from i. Now, if you don’t assign j to i in the 7day pass for loop, then i will change But we need same i for 30 days pass loop.
Make sure you first understand the DP concepts playlist - I have explained from basics of DP th-cam.com/play/PLpIkg8OmuX-JhFpkhgrAwZRtukO0SkwAt.html&si=v0aelqRqzzr1nYd5
Bhaiya mai abhi graph padh rha hu lekin last ke 2potd dp ke the maine recursion and memorize approach samjh aa gya to mai bottom bhi dikhu ya dp karne ke baat dikhu??
Hii bhaiya mein ne aapse dp padhna start kiya and ab mein questions solve karr paa rha hu. I am very happy actually starting mein question samajh nahi aaya to aapke video se question samajh liya and then mein recursion+ memorization try kiya and vo completely execute hogya and jab mein ne aapka solution dekha to same to same code nikla. Thank you so much bhaiya for this wonderful explanation. Mein bohot saare jaano ke videos dekhta hu but aapka solution kafi informative lagta hai kyuki aap WHY pe kafi focus karte ho and meri saari curiosities aap clear kar dete ho. Thank you so much bhaiya for this wonderful video solutions it helps me a lot to solve the questions. Mein ne striver and Aditya verma ke saare videos dekhe and samajh bhi pura aaya but feel nahi aati thi and questions bhi solve nahi hote the but aapke case mein aisa nahi hai questions mein solve karr paa rha hu
This means a lot ❤️🙏😇
💯
Very rarely people go to depth of each and every minute detail.
You are one of them and it is clearly seen in your masterpiece explanation.
Pata bhi nhi chala video kaise khatam hogaya , excellent explanation + jo apne decision tree karke samajaya na wow
Thank you so so much Pritish.
You guys comment and appreciate my work, that makes my day ❤️
class Solution {
public:
int dp[366];
int f(int index, vector &days, vector &costs){
if(index >= days.size())
return 0;
if(dp[index] != -1)
return dp[index];
int od= days[index]+1;
int lb= lower_bound(begin(days),end(days),od)-begin(days);
int f1= costs[0]+ f(lb, days, costs);
int sevenday= days[index]+7;
int lb2= lower_bound(begin(days),end(days),sevenday)-begin(days);
int f2= costs[1]+f(lb2, days, costs);
int thirtydays= days[index]+30;
int lb3= lower_bound(begin(days),end(days),thirtydays)-begin(days);
int f3= costs[2]+f(lb3, days, costs);
return dp[index]= min({f1,f2,f3});
}
int mincostTickets(vector& days, vector& costs) {
memset(dp, -1, sizeof(dp));
return f(0, days, costs);
}
};
My approach using lower_bound instead of looping in the function call.
Runtime: 0 ms, faster than 100.00% of C++ online submissions for Minimum Cost For Tickets.
Wonderful
You Nailed It bhai 🔥
I just saw till 8:27 timestamp, bcz you made the problem statement simplified , i solved the rest of it on my own ! LC DESCRIPTION IS little confusing ,....thanks you deserve best!
If it is in my hand i would have made ur subscribers 20million + u deserve it .......i was a huge fan of striver i thought no one could make questions this much easier other than striver but then i saw one of ur video by chance and from then i forgot striver i just need everu topic to br covered by uuu ...u r just awesome sir.....
Thank you for all the love and trust.
It means a lot to me 🙏❤️
Samee❤
💯💯💯
MIK sir is not a teacher, he is a Magician..... that's why he is different...
Respected MIK Sir,
1. I understood concept.
2. Paused video at 20:24
3. Drawn recursion tree diagram on my own.
4. Coded recursion and recursion + memoization on my own.
5. Runtime: 0 ms, Beats: 100%
All credit goes to your teaching and your efforts in teaching us.
Here's my Java recursion code:
int[] dp;
private int mincostTicketsRecursionMemoization(int[] days, int[] costs) {
dp = new int[days.length + 1];
Arrays.fill(dp, -1);
return solveRecursionMemoization(days, costs, 0);
}
private int solveRecursionMemoization(int[] days, int[] costs, int index) {
if (index >= days.length) {
return 0;
}
if (dp[index] != -1) {
return dp[index];
}
int costOfOneDayPass = costs[0] + solveRecursionMemoization(days, costs, index + 1);
int costOfSevenDayPass = costs[1] + solveRecursionMemoization(days, costs, getIndexOfNextDay(days, index, days[index] + 7));
int costOfThirtyDayPass = costs[2] + solveRecursionMemoization(days, costs, getIndexOfNextDay(days, index, days[index] + 30));
return dp[index] = Math.min(costOfOneDayPass, Math.min(costOfSevenDayPass, costOfThirtyDayPass));
}
private int mincostTicketsRecursion(int[] days, int[] costs) {
return solveRecursion(days, costs, 0);
}
private int solveRecursion(int[] days, int[] costs, int index) {
if (index >= days.length) {
return 0;
}
int costOfOneDayPass = costs[0] + solveRecursion(days, costs, index + 1);
int costOfSevenDayPass = costs[1] + solveRecursion(days, costs, getIndexOfNextDay(days, index, days[index] + 7));
int costOfThirtyDayPass = costs[2] + solveRecursion(days, costs, getIndexOfNextDay(days, index, days[index] + 30));
return Math.min(costOfOneDayPass, Math.min(costOfSevenDayPass, costOfThirtyDayPass));
}
private int getIndexOfNextDay(int[] days, int index, int totalDaysCanBeCovered) {
while (index < days.length && days[index] < totalDaysCanBeCovered) {
index++;
}
return index;
}
Java Implementations:
Recursive (TLE):
class Solution {
private int solve(int days[], int costs[], int n, int idx) {
if(idx >= n) return 0;
//one day pass at ith index
int cost1 = costs[0] + solve(days, costs, n, idx+1);
// two day pass
int j = idx;
int max_days = days[idx] +7;
while(j < n && days[j] < max_days) {
j++;
}
int cost7 = costs[1] + solve(days, costs, n, j);
// 30 days pass
j = idx;
max_days = days[idx] + 30;
while(j < n && days[j] < max_days) {
j++;
}
int cost30 = costs[2] + solve(days, costs, n, j);
return Math.min(cost1, Math.min(cost7, cost30));
}
public int mincostTickets(int[] days, int[] costs) {
int n = days.length;
return solve(days, costs, n, 0);
}
}
Memoization:
class Solution {
private int solve(int days[], int costs[], int dp[], int n, int idx) {
if(idx >= n) return 0;
if(dp[idx] != -1) return dp[idx];
//one day pass at ith index
int cost1 = costs[0] + solve(days, costs, dp, n, idx+1);
// two day pass
int j = idx;
int max_days = days[idx] +7;
while(j < n && days[j] < max_days) {
j++;
}
int cost7 = costs[1] + solve(days, costs, dp, n, j);
// 30 days pass
j = idx;
max_days = days[idx] + 30;
while(j < n && days[j] < max_days) {
j++;
}
int cost30 = costs[2] + solve(days, costs, dp, n, j);
return dp[idx] = Math.min(cost1, Math.min(cost7, cost30));
}
public int mincostTickets(int[] days, int[] costs) {
int n = days.length;
int dp[] = new int[366];
Arrays.fill(dp,-1);
return solve(days, costs, dp, n, 0);
}
}
Bottom up/ Tabulation:
class Solution {
public int mincostTickets(int[] days, int[] costs) {
Set st = new HashSet();
for(int day : days) {
st.add(day);
}
int lastDay = days[days.length - 1];
int dp[] = new int[lastDay+1];
//dp[i] = min cost required to travel till i th day of your travel plan
dp[0] = 0;
for(int i=1; i
that t[max()] method just made me so excited and motivated to learn more, its like that OMG moment I used to have when I leant about a lot of new stuff in Engineering physics. One day expecting to reach that level of smartness to make neat and beautiful code.
Indeed ❤️
It feels good when you start solving questions like your teacher ....solved it by myself thanks btw
The best explanation 👍
Another Recursive + Memoization way using set
class Solution {
public:
int solve(vector& days, vector& costs, unordered_set& st, vector& dp, int idx) {
if(idx > 365) return 0;
if(dp[idx] != -1) return dp[idx];
if(st.find(idx) != st.end()) {
int op1 = costs[0] + solve(days,costs,st,dp,idx+1);
int op2 = costs[1] + solve(days,costs,st,dp,idx+7);
int op3 = costs[2] + solve(days,costs,st,dp,idx+30);
return dp[idx] = min(op1, min(op2,op3));
}
else {
return dp[idx] = solve(days,costs,st,dp,idx+1);
}
}
int mincostTickets(vector& days, vector& costs) {
unordered_set st;
vector dp (366,-1);
for(auto& day : days)
st.insert(day);
return solve(days,costs,st,dp,0);
}
};
Super and easy Explaination! perfect! Thank you...
Absolutely one of the best nd understandable approach
Thanks a lot 😇
Bahut Acha padhate ho bhaiya explanation bahut acha hai
Best explanation❤as usual
We can also use lower bound to reach index
Nowdays I likes your videos before watching it because i know it will be awesome anyway
Means a lot ❤️
You are the best MIK
How you can make so perfect recursion tree ,,, even after watching ur whole videos i tried to make trree by myself ,,, i forgot small things like what is index what will come inside node and blah blahh .... You are genius :)
We all will grow together and rock 💪
Thank you so much Shashwat
And ..... a very Happy New Year !
This video is a goldmine to me.
Thanku mik, just trying to be consistent for 2025
You have a really good way of explaining things out. Good work brother. Btw can you please upload some more questions on recursion and backtracking.
Thanks a lot Aditya.
And sure, more coming on Recursion and Backtracking
great explnation , amazing bro , very good explnation
well explained! Thank you so much sir..
I was able to do it by my own today, but came here to see if we can do it using just three variables because current value only depends on previous1, previous7 , previous30. I did it using 1d dp
Sir this is insane🔥, if possible plz post gfg potd also.
Thanks a lot.
Will soon start including gfg potd
yes please...including gfg potds will be really helpful
another great explaination :)
worth watching till the last min
sir how do you build the intuition with ease
You have got some great teaching skills
Thanks a lot Anup ❤️
Bottom up just OP ❤
❤️🙏
Bro leetcode - 1171 & leetcode - 92 pls make a video on it.
I'm requesting you from the last 2 weeks.
Brining it soon.
Having a tight schedule these days.
Bhaiya aap iiest shibpur se padhe ho . aap bengali ho ?
Hindi version of striver😊
I thought of dp but implementation failed
best
great video , but why are dp vidoes not organised they are random
Hi there,
Actually this is a problem playlist and contains only questions. There is a separate playlist for dp concepts where it’s organised topic wise.
I usually create two playlists for every topic :
1) Concepts Playlist - Contains from basic concepts to expert concepts.
2) Popular Interview Problems playlist.
I have created concepts and interview problems playlist for
1) Graph
2) Recursion
3) DP
4) Segment Tree
Planning soon to create concepts playlist for Tree as well.
Graph Concepts - th-cam.com/play/PLpIkg8OmuX-LZB9jYzbbZchk277H5CbdY.html&si=lZG2IJTmSW4kRrx-
Graph Popular Interview Problems - th-cam.com/play/PLpIkg8OmuX-I_49pdy1XFY6OcATnxUrrO.html&si=CG2JvGWVmvoSqvWA
Recursion Concepts - th-cam.com/play/PLpIkg8OmuX-IBcXsfITH5ql0Lqci1MYPM.html&si=614iI4NyHY-FTeJH
Recursion Problems (In progress) - th-cam.com/play/PLpIkg8OmuX-IXOgDP_YYiJFqfCFKFBDkO.html&si=88fBhRnr62OYTnDP
DP Concepts (In progress) - th-cam.com/play/PLpIkg8OmuX-JhFpkhgrAwZRtukO0SkwAt.html&si=laFVYy6ep2BkOg0s
DP Popular interview problems - th-cam.com/play/PLpIkg8OmuX-L_QqcKB5abYynQbonaNcq3.html&si=VHEn9b-wqTnAVyyi
Segment Tree Concepts -
th-cam.com/play/PLpIkg8OmuX-K1qUIQToCllUO0UIKXt8dB.html&si=xm7DqRN4H0eZwna4
I have on doubt in bottom up approach. for example we suppose days[]={1,4,6,7,8,15,20,38,44,45} now you said if i am on 45 then i must came from 15th , 38th or 44th day via 30 days, 7 days or 1 day pass respectively. But suppose if i came at 45th day by using a 30 day pass when i was at 20th day(6th index) then where is this case is handled i mean in those three cases which you have tought we are reaching reaching at destination when we were exactly before 1 day or 7 days or 30 days but what about this case. Can you please explain
Please start DP and Graph playlist
Graph Playlist : th-cam.com/play/PLpIkg8OmuX-LZB9jYzbbZchk277H5CbdY.html
(More will be added)
DP concepts playlist coming soon
sir this is how i solved todays POTD:
class Solution {
public:
int t[367][53001];
int solve(vector& temp, vector& costs,int i,int amount){
if(i >= temp.size()){
return amount;
}
if(t[i][amount] != -1){
return t[i][amount];
}
if(temp[i] == 0){
return t[i][amount] = solve(temp,costs,i+1,amount);
}
int cost_0 = solve(temp,costs,i+1,amount+costs[0]);
int cost_1 = solve(temp,costs,i+7,amount+costs[1]);
int cost_2 = solve(temp,costs,i+30,amount+costs[2]);
return t[i][amount] = min({cost_0,cost_1,cost_2});
}
int mincostTickets(vector& days, vector& costs) {
vectortemp(366,0);
for(auto day : days){
temp[day] = 1;
}
memset(t,-1,sizeof(t));
return solve(temp,costs,0,0);
}
};
unordered_set does not have .back() property
He is using .back() in vector.
Bhaiya system design playlist me aur content aaega
And aapne intermediate wali me code kyu nhi kiya ?
Generals the coding is not often asked in system design because system design is more of a discussion interview about ideas and different approaches.
And more Interview system design videos are coming soon on intermediate playlist
@@codestorywithMIK ok I find your explaination and continuation of video linking very amazing
Good work appreciate 💯💯
Thank you so so much
I didn't understood the memoozation part. Can anyone please exlplain?
Bhai a request, please make a video on leetcode 2218 if possible. It will cover unbounded knapsack type of dp
Sure, let me keep a note for this
Bhaiya system design wale playlist ka notes available hoga kya??
Not as of now Pratik.
But soon i will try to put then in a PDF
@@codestorywithMIK thank you bhaiya ❤️
Bhai can you please tell me why we are storing i into j.I just want to know the logic behind it.
Because if you notice you need try for 7 days pass from i
And 30 days pass from i.
Now, if you don’t assign j to i in the 7day pass for loop, then i will change
But we need same i for 30 days pass loop.
@@codestorywithMIK ok shukriya bhai♥️
Bhaiya please start teaching dp i have zero idea about it
Soon coming
bro aapne time complexity explain nahi ki aaj k POTD mai
Actually this is an old video. I missed during that time ❤️
Do check the github link in the description, it contains time and space mentioned
in search of gold, i found diamond.
Means a lot to me 🙏
idk why i am not able to write Bottom UP solution.
Make sure you first understand the DP concepts playlist - I have explained from basics of DP
th-cam.com/play/PLpIkg8OmuX-JhFpkhgrAwZRtukO0SkwAt.html&si=v0aelqRqzzr1nYd5
longest video I've ever watched on YT.
Aaram kro aaram se😂
Exceptional 🤌🏼
Thank you so much 😇❤️
Bhaiya mai abhi graph padh rha hu lekin last ke 2potd dp ke the maine recursion and memorize approach samjh aa gya to mai bottom bhi dikhu ya dp karne ke baat dikhu??
bhaiya bina dp padhe dp k question kar liya sirf 2 din ka potd samjh kar
😱🔥🔥🔥