Two Best Non-Overlapping Events | Brute Force | Better | Leetcode 2054 | codestorywithMIK

[@anonymoushackerar7507]

Bro one request, never ever stop making videos, never bro. you are more helpful to us than any other big course sellers out there on market. Its because of you my problem statement thinking is being transformed day by day.

[@FanIQQuiz]

Yes 🙌 Please never stop making videos MIK

[@hana_0712]

Yes very much true

[@sanvisingh9512]

Been searching for the correct explanation and as usual yours is best. Thank you so much!!

[@codestorywithMIK]

Means a lot to me. Happy it helped! 🙏😇

[@EB-ot8uu]

same

[@ayushmanbaghel7659]

could you provide ur linkedin url

[@sanvisingh9512]

@@ayushmanbaghel7659 whose,code story with mik?

[@ravirathore6717]

Yeah his explanation is quite good.

[@rajashreeparhi1549]

I solved it using brute force initially. Then, I thought of a take/non-take approach, but I was unsure how the other greater values would be added when finding the next index. For example, in this test case: events = [[1, 3, 2], [1, 5, 5], [4, 6, 7], [8, 9, 8]] For the event [1, 3, 2], the next upper bound is [4, 6, 7]. I wondered how [8, 9, 8] could also be added to [1, 3, 2], as that is a valid combination. Then, I drew the recursion tree and realized that since the events are sorted, finding the first upper bound ensures that the "not take" branch will handle the remaining cases. For a moment, I felt both happy and surprised to have understood this concept! Thanks for explaining. Today marks my 7th day of solving POTD (Problem of the Day), and I’m thoroughly enjoying this journey! Though for last 3d I referred your vids to solve it, I hope one day I can do it on my own!

[@mannusharma4620]

Bro your motivation line before starting any problem is becoming my daily dose of motivation in life ❤️

[@ravirathore6717]

MIK Sir, your explanation is so clear and to the point. Thanks for sharing.

[@study-yd6es]

Amazing lecture !!! Please keep uloading these amazing lectures of POTD!!!

[@B-Billy]

Bhai you are the reason I believe one day (Insha Allah) will crack a big company❤🎉

[@DeadCode_Debugs]

this is really good problem...for logic development

[@logicoverflow1240]

I appreciate the way you beautifully explained the solution. Watched too many videos on this problem but you explained in Desi way 🙏🏻

[@hana_0712]

Thank you for the great explanation.

[@souravjoshi2293]

Ab aisa lagta hai ki mai Leetcode Medium problems banaleta hu without much problem. I have seen this change after consistently solving potd for last 5-6 months. Thanks to you for keeping us consistent

[@EB-ot8uu]

After doing some mistakes and a hint, I solved it. All thanks to you LEGEND MIK

[@jain5184]

mik bhaiys thnkku so much by following u i had solved with brute force and i happy becoz i never try to solve prob on my own but this first time i solved brute force in 40 min moving frd to the video for the optimal sol once again thnku so much

[@FanIQQuiz]

Honestly speaking, i am now able to solve Medium level Qns 70-75% times. But I always come to your videos to support you and to learn something new. You are the best ❤

[@darshitgajjar5199]

Bro you are really Great. pls be consistent and me also consistent. one day will get our dream JOB. The motivation quote in the beginning really great. I share with my 5 friends. they'll subscribe ur channel

[@hare_krishna8411]

raadhe raadhe bhaiya ...❤

[@wearevacationuncoverers]

laajawab . Love you MIK

[@omgupta777]

Thanks sir , maza aaya

[@gui-codes]

I was able to do brute force (ofcourse that was very easy). Thanks for the minute details as always.

[@aizad786iqbal]

thanks man, greedy please make once you are back.....

[@utkarshsinghchouhan8819]

Bhai never stop doing the "motivation quote" part of the videos. I think everyone can solve DSA but teaching is an art not everyone can motivate others. Having said that there is this quote I try to live by "Kismat ke bharose rehne waalo ko woh har cheez milti hai, Jo mehnat karne wale thuk jaate hai"😅...it's just me.

[@study-yd6es]

7th day completed of POTD!!!!

[@DivyanshKUMAR-e1m]

Hey can you please explain with sweep line algo plz it's a vary good algo for any overlapping type problem. I never able to understand this concept in depth Please please please make a video on it

[@rockykumarverma980]

Thank you so much Bhaiya ji 🙏🙏🙏

[@Ajayslayer278]

Hi Sir, I've really enjoyed your videos, especially the bit manipulation and tries playlists! I feel much more confident in those topics now. I understand that this video belongs to the arrays playlist, but could it be possible to create a separate playlist for 'interval' type questions? That would be really helpful!. Thank you sir. 😇

[@sauravchandra10]

Initially, it seemed like an easy take - not take a problem, but when I started to implement it, I came across a few issues: 1. How do we keep track of the number of intervals chosen -> keep a count variable 2. How to keep track of the last interval chosen -> keep track of the ending time of the last interval chosen 3. How to memoize -> memoise index, end time, and count But the solution had two major issues: 1. Without sorting, the code gave the wrong answer for this test case: [[66,97,90],[98,98,68],[38,49,63],[91,100,42],[92,100,22],[1,77,50],[64,72,97]] 2. Even after sorting, the code gave MLE since end times go up to 10^9. This is where I got stuck. Saw the hints, saw BS, and tried to implement it but couldn't figure out on what basis to sort the intervals - start time, end time, or the value. But it was very easy, just had to start take - not take from the first valid index. Silly of me to not figure it out. Here is the code that gave MLE: class Solution: def maxTwoEvents(self, events: List[List[int]]) -> int: events.sort() dp = {} def recur(ind, lastAttended, totAttended): if ind == len(events): return 0 if (ind, lastAttended, totAttended) in dp: return dp[(ind, lastAttended, totAttended)] ans = recur(ind+1, lastAttended, totAttended) if events[ind][0] > lastAttended and totAttended < 2: ans = max(ans, events[ind][2]+recur(ind+1, events[ind][1], totAttended+1)) dp[(ind, lastAttended, totAttended)] = ans return ans return recur(0, 0, 0)

[@codestorywithMIK]

Thanks for sharing your thought process.

[@DineshKumar-gt7xm]

Please make videos on contest questions as well specially 3rd and 4th.

[@FutFreaKKKKK]

greedy bhi bana dijiye sir

[@himadrinath1502]

priority queue is best solution.

[@FutFreaKKKKK]

@himadrinath1502 do you have the solution? If yes , share the link please!

[@bhuvan6926]

Broo..... I did it my own... Because of you only bro... After reading the problem statement, the question is striked in my mind which is max profit in job scheduling which was explained by you.... Thank you so much bro.... ❤ You are the reason for thinking my onw☺️

[@Anime-ub7vs]

Bhaiya greedy approach pe bhi video bana do

[@akashsonar6332]

I used Segment Tree to solve the problem, the code is working fine but it gave Memory limit exeded.

[@floatingpoint7629]

Please make a video on greedy approach, the line sweep algorithm is not very obvious

[@bhushanambhore8378]

Bhai please if possible make video on greedy approach of this problem as it is getting hard for me to understand the memorization here..Also Thank you for this video...

[@HumanBeing-m1x]

waiting for your manacher's algoirthm, z algorithm and rabin karp for string matching thank mazhar bhai

[@doomedlili5942]

Thanks Mik I was followed your videos for just 2 months and then become inconsistent due to some reasons but when i thought to solve this ptod i was able to think and solve just minor mistake i done i searched using linear like in dp function itself so it resulted TLE for TC 40 . But through your video i corrected that. Thanks for all this effort ...

[@morty6456]

bhai please aur approaches bhi discuss krlo iski

[@aush3212]

Bhaiya Video Jaldi Dala Karo Yarr Subaha Se Wait Kar Raha Hu Apke Video Ka😅

[@codestorywithMIK]

Apologies for delay today. Actually i always go out during weekends (travel or road trip) . Will take care of this going forward ❤️🙏😇

[@StriveSphere430]

Ek din ayega jab hum kisiko sunayenge, "Once upon a time, there was a storyteller jo humein kahani sunata tha, aur humne uski kahani se hipnotised hokar poora LeetCode complete kar die the !" unki baat mein ek ajeeb si jadugari thi jo humein apni mehnat aur lagan ko ek naye nazariye se dekhne ke liye majboor kia tha !

[@ashishnagarse7348]

Bhai ek line sweep method pr video bana do :)

[@tushargulati1327]

in this part if(count==2 || index>=events.length){ return 0; } jab count 2 ke equal ho jaae hume Math.max(take, not_take) return krna chahea na??

[@omgupta777]

Bro jb count 0 tha tb humne ek event include Kiya and count ka value kiya count +1 then jb count 1 hua tb jaakr humne 2nd event include Kiya and after that the count value became 1+1 = 2, now that we have included 2 events , we won't go any further and that's why when count = 2 , we return 0

[@raj-thombare]

Hi, one request if can you please change that black background to white and use black pen to draw and explain! otherwise it puts a lot of strain on eyes

[@vaibhav454]

@codestorywithMIK Make others approach for this ques

[@JeetuKumar-wd1uw]

Bhaiya leetcode contest ka solution karwo

[@gauravparasar4571]

bhiyaa aap har question kar lete ho yrr kese kitna time lagega apke jesa banne me

[@cheeze8464]

Bhai binary search ki jagah agar hm i + 1 pass kr rhe h toh wrong output kyon aa rha h??

[@gui-codes]

bhai kyoki agar tumne ith event choose kara hai to next event i+1 wala le paoge ya nahi ye sure nahi hai na kyoki wo overlap bhi to ho sakta hai last selected event se.

[@prasadgaikwad9938]

@@gui-codes but what if we pass prev endtime in recursion and put a check before we take next event if(events[i][0] > prevendtime)? it still gives wrong input why?

[@manasivaidya2623]

bhaiya used BS to find second val index and a precomputed vector which give greatest value from right class Solution { public: int bs(vector& events, int low, int high, int target) { int value = -1; while (low target) { value = mid; high = mid - 1; } else { low = mid + 1; } } return value; } int maxTwoEvents(vector& events) { int n = events.size(); sort(events.begin(), events.end()); vector pre(n, 0); pre[n - 1] = events[n - 1][2]; for (int i = n - 2; i >= 0; i--) { pre[i] = max(pre[i + 1], events[i][2]); } int result = 0; for (int i = 0; i < n; i++) { int start = events[i][0]; int end = events[i][1]; int val = events[i][2]; int bsVal = bs(events, i + 1, n - 1, end); if (bsVal != -1) { val += pre[bsVal]; } result = max(result, val); } return result; } };

[@gui-codes]

Mere man me aisa kuch aya tha but mai implement karne me stuck hogaya tha. Thanks for sharing

[@ayushmanbaghel7659]

I solved this problem by watching your job Scheduling video . My Code -> class Solution { public int getNextIndex(int arr[][],int left,int prevEnd){ int right=arr.length-1; int result=arr.length+1; while(leftprevEnd){ result=mid; right=mid-1; }else{ left=mid+1; } } return result; } public int solve(int arr[][],int i,int dp[][],int count){ if(count>2){ return Integer.MIN_VALUE; } if(i>=arr.length){ return 0; } if(dp[i][count]!=-1){ return dp[i][count]; } int next=getNextIndex(arr,i+1,arr[i][1]); int taken=arr[i][2]+solve(arr,next,dp,count+1); int notTaken=solve(arr,i+1,dp,count); dp[i][count]=Math.max(taken,notTaken); return dp[i][count]; } public int maxTwoEvents(int[][] events) { Arrays.sort(events,(a,b)->Integer.compare(a[0],b[0])); int dp[][]=new int[events.length][3]; for(int row[]:dp){ Arrays.fill(row,-1); } return solve(events,0,dp,0); } }

[@sarangkale6761]

Sir shyad aapka question name youtube title par galat hoo gaya hai

[@codestorywithMIK]

corrected ❤

[@arabindaparida4075]

Nehi banta sir 😢

[@xendu-d9v]

even hard for me, the thing is before code, we should have clarity on solution, practice more

[@tusharmore3860]

I am getting TLE in python code. class Solution: def maxTwoEvents(self, events: List[List[int]]) -> int: n = len(events) events.sort() cache =[[-1] * 2 for _ in range(n)] # (i , count) = ? def binarySearch(i, key): l = i r = n - 1 while l key: r = mid - 1 else: l = l + 1 return l def helper(i, count): if count >= 2 or i >= n: return 0 if cache[i][count] != -1: return cache[i][count] nextIndex = binarySearch(i + 1, events[i][1]) pick = events[i][2] + helper(nextIndex, count + 1) skip = helper(i + 1, count) cache[i][count] = max(pick, skip) return cache[i][count] return helper(0, 0)

[@prasadgaikwad9938]

please explain why this way of dp dont work and give right answer? int rec(vector& dp, vector& events, int k, int ind, int prevtime) { if (ind == events.size() || k == 2) return 0; if (dp[ind][k] != -1) return dp[ind][k]; int take=0; if(events[ind][0] > prevtime){ take = rec(dp, events, k + 1, ind+1,events[ind][1]) + events[ind][2]; } int nottake = rec(dp, events, k, ind + 1,prevtime); return dp[ind][k] = max(take, nottake); } int maxTwoEvents(vector& events) { int ans = 0; sort(events.begin(), events.end()); vector dp(events.size(), vector(3, -1)); ans = rec(dp, events, 0, 0,0); return ans; }

[@3mbgaming444]

First comment

[@codestorywithMIK]

❤️

[@3mbgaming444]

Sir may abhi MCA kay Final semester may hu any tips for crack a service based company?

[@jeehub041]

Always your fan bhaiya ❤❤

[@codestorywithMIK]

Means a lot to me 😇❤️🙏🙏🙏

[@anshul3112_]

Priority queue Approach: class Solution { public: int maxTwoEvents(vector& events) { sort(events.begin(),events.end()); vector endTimeSorted = events; sort(endTimeSorted.begin(),endTimeSorted.end(),[](vector &a, vector &b) { return a[1]

[@xendu-d9v]

heading is wrong, thumbnail is fine

[@codestorywithMIK]

Corrected ❤️

[@arnabsarkar5245]

Almost did this problem, but couldn't get the sorting wala logic. Thank you bhaiya 🫠

[@raj-thombare]

Hi, one request if can you please change that black background to white and use black pen to draw and explain! otherwise it puts a lot of strain on eyes