Minimum Cost For Tickets - Leetcode 983 - Python

[@bhoumik8548]

The solution becomes much easier when you know what not to do, rather than just knowing what to do. Ur videos are the only thing i watch when i dont feel like doing leetcode.

[@ajitpalsingh606]

same

[@johnniewalkerjohnniewalker2459]

Happy New Year with a lot of health!!!

[@qsvui]

what happened to the little drawings you'd make for your thumbnails? those were cute!

[@business_central]

agree! missed them

[@NeetCodeIO]

Added a Big-O cheatsheet to NeetCode today: neetcode.io/courses/lessons/big-o-notation It's free and mobile friendly.

[@NeetCodeIO]

Here's the code from today's problem in other languages: neetcode.io/solutions/minimum-cost-for-tickets

[@CodeSnap01]

why here?

[@yashwanthsai762]

Thank you

[@rohitkumaram]

16:40 some people don't like it, I am that some people. but I like your explanation, order doesn't matter when u explain it so well.

[@travian821]

I tried to keep track of the "free days" that a 7 days or 30 days pass would allow you in the dynamic programming cache. The run time increased a lot. I struggle with defining the minimum necessary of variables to solve a problem, i keep some just in case.

[@MP-ny3ep]

Very beautifully explained. Thank you

[@arunitbaidya6118]

the goat back at it again

[@nicholaschow5734]

Regarding the greedy approach w/ two decisions, I do not think it will work. Take this example: days = {1, 5, 12, 30} tickets= {2, 3} Purchasing a day pass for each day we get 2+2+2+2 = 8 [ One ticket per day ] Purchasing a 7 day pass b/c it's larger: 3 + 3 + 3 = 21 [ Buy on the 1st day, 12th day, then 30th day ] In this situation, choosing the smaller ticket each time is far superior than getting the 7 day pass. If greedy approach is to purchase the larger day pass then it will be insufficient if the next time you need a ticket exceeds the number of valid days for the ticket ( i.e. more than 7 days between traveling)

[@business_central]

Just sharing an opinion cause you asked about our thoughts yesterday on the re-upload thing. I think it's not necessary as I usually check in both your channels if video is already available for that problem. I think in days were there are problems already addressed, it would be great if you could go back in the daily challenges to one of the problems you skipped as you didn't have time for it, and just do a video on that instead. There are still so many ones in the daily challenges that we skipped and to be honest no one explains as good as you. Would love to see that. A part for this, thank you for all your efforts!

[@nihalbhandary162]

Instead of iterating over and over again to find the day within the window. You could use a pointer variable to keep a track of the days which are within 7 and 30. That way this gets more fast. dp = [0]*(len(days)+1) k,j =0,0 dp[0]=0 for i in range(len(days)): while days[i]-days[j]>=30: j+=1 while days[i]-days[k]>=7: k+=1 dp[i+1]=dp[i]+costs[0] dp[i+1] = min(dp[k]+costs[1],dp[i+1]) dp[i+1] = min(dp[j]+costs[2],dp[i+1]) #print(dp) return dp[len(days)]

[@Hoppitot]

I iterated for the 7 days but used binary search for the 30 day. I guess this is another way.

[@nihalbhandary162]

@@Hoppitot That's what I thought initially to use binary search. But then I remembered if the for some ith value, the maximum extent for 7 day window is j, then for (i+1)th value, it is going to be somewhere right of j. I dont need to use binary search for such small windows.

[@tejas1531]

Thanku Bhaiya. I thought the top down but not much properly so i won't be able to code it. But after 1hour and 30 min i came up with bottom up. It helped me to understand how i could have thought for the top down so thank you

[@viveksingh9223]

It's like a variation of coin change.

[@VarshilNarola]

I think most efficient solution is O(N) time where N is length of days and O(30+7) space which is technically O(1) space but your solution is O(N*30) time and O(N) space which in this case is worse then logN factor

[@NeetCodeIO]

It depends on the input doesnt it? The O(n) you describe is actually O(365), where as my n is technically the actual input size, which will often be less than 365. That's why the runtime of my algo was still efficient.

[@VarshilNarola]

@ no brother my N is length of days I have mentioned clearly. It is input only. So my solution will work even if days[i]>10^9. In below month and week are only pointers and will atmost traverse through days at max once. So time complexity is O(N) where N is length of days and space complexity is O(30) ~ O(1) N=len(days) dp=[0]*(30) month=week=N for i in range(N-1,-1,-1): while days[i]+30-1

[@NeetCodeIO]

@@VarshilNarola oh okay understood, yeah i think this optimization is covered in the code solutions on NC neetcode.io/solutions/minimum-cost-for-tickets i thought you were talking about the max(days) solution

[@VarshilNarola]

@@NeetCodeIO Yes it is covered and solutions are quiet comprehensive. Thank you!!

[@RayTracingX]

While I have solved 250+ questions on LeetCode, this question is extremely difficult for me, also code part seemed tricky, I spent 40 minutes to only understand problem description😞😞😞