Merge Intervals | Leetcode | Problem-6 | Brute-Optimal | C++/Java

[@takeUforward]

Please watch the new video which covers it in more depth, and also prints it: kzbin.info/www/bejne/f5bbf2lmoJtloNE How is the new thumbnail, should we keep it for all ? As always, if you understand, make sure you drop "understood" in the comment section, if you have doubt, drop that in, will revert :) . If you appreciate the channel's work, you can join the family: kzbin.info/door/JskGeByzRRSvmOyZOz61igjoin

[@amankrsingh]

Old one was very Good

[@pranshukumarsingh7653]

Understood

[@vinayduggal2433]

@take U forward Pls. Reply striver bro . Bro I am currently coding in python but as u say in ur video that 85 percent people do coding in c++. And also some companies doesn't allow python during interview . May I go for c++(stl) or continue in python. I am now in final year of b.tech

[@VijayKumar-bk9bq]

sir make a video in hindi...pleade sir..

[@vaibhavsethia70]

Understood

[@sandeepnallala48]

you are not striver , you are SAVIOUR : ) love ur lectures brother : )

[@mrsmurf911]

(a[i]==b[j] and (b[j]==c[k]))

[@paridhijain7062]

this video is so well explained and I got each and every point of it. Referring Striver sheet along with this video. Thank you striver for making such wonderful content for us.

[@GaneshBhutekar-nu1gd]

i did the same thing without any tutorial now i am feeling confident

[@vaibhavyadav1787]

You don't know how much you're helping us..... God bless you brother....

[@gouravmallick27]

this was the most efficient explanation, thanks, sir.

[@tanmaychandra9434]

Great effort Man we can learn alot from you there are several people who keep their all learnings within themselves but you came out and kept on sharing your knowledge . Great respect man.

[@aditya-bl5xh]

Want to be as dedicated as he is, he got a job then also he's helping us, great! Thank you so much bro

[@GauravKumar-bk7hh]

bro mujhe coding se thora dar lagta hai. agar main koi problem karne baithta hue to logic click hi nahi hota. main bhi chahata hue ki apna 100% dun per wo interest nahi aa pata

[@sannidhayvashal9806]

@@GauravKumar-bk7hh Why are you coding then ? If you don't enjoy the process then you are in the wrong field.

[@harshupreti1526]

@@GauravKumar-bk7hh solution samjhne ke baad bhi maza ni aata toh chod de

[@viggicodes]

I disable ad blocker and watch your videos. Keep up the good work striver !!

[@nivedithat4745]

After watching video halfway through, I thought how lucky the current 2nd years and 3rd years are… they can watch the entire playlist in 10 days and voila!!! ready for cracking companies

[@rajeevsingh5453]

m in 3rd year and m thinking the same for 1st and 2nd year.

[@maitrishmandal_3139]

m in 2nd year and m thinking the same for 1st year.

[@ash-gt]

m in 1st year and m thinking the same for class 12th

[@HARIHaran-ks7wp]

@@ash-gt my in womb and thinking the same for previous birth

[@pranayreddy5824]

I am 12th and thinking of 6 year old chintu how lucky he is...😂 just kidding i am b-tech final year

[@ifzagul2760]

Your method to teach is astonishing.

[@araragikoyomi7186]

I solved the brute force using graph by creating components of intervals which are overlapping and finding minimum and maximum range and insert it in the ans

[@annawilson3824]

we are comparing the first interval with itself, can avoid it. O/w, great job!

[@vishalm784]

I think the brute force approach doesn't require sorting at all and would have time complexity O(n^2). First, we merge all the interval pairs that overlap and add to an array and form a result. Then we do it recursively to find if there's still some more merging possible and if not return the result. But surprisingly this algorithm is faster than the optimal solution mentioned. LeetCode result : Runtime: 2 ms, faster than 99.47% of Java online submissions for Merge Intervals. This is the version I implemented :- public int[][] merge(int[][] intervals) { int n = intervals.length; boolean included[] = new boolean[n]; ArrayList arr = new ArrayList(); for(int i = 0;i

[@RahulSharma-jl3xd]

[@dhananjaysingh3675]

True ..ths what confused me too.. If intervals are already sorted then why check the remaining list of intervals, if one of the subsequent interval is already found non merging..

[@vamshikrishnareddy2313]

also can be solved by using prefix sum, array between (1, and max), considering edge cases and space

[@nishantmohanty2147]

Bhai apana bahut bhala kama karuchanti. Apana bahut bhala teacher.

[@subhamkumar1432]

Explanation is extremely understandable and convenient:)

[@freshcontent3729]

can you please write the bruteforce cpp code of this which is shown in this video? i tired to implement that approach but getting stuck, please help

[@amarjeetkumarsingh733]

This is your best explanation I have ever seen

[@Aditya-karn9]

What you are doing is fabulous. I understand every concept that you are teaching. Can you make a video on Closest Palindrome problem, as i don't find any satisfactory video of this problem.

[@nehasagar9416]

Understood🔥....I love ur videos And I loved the previous thumbnail. Thank you so much for helping us with everything ♥️

[@arup_creations3545]

We can also perform the optimised approach in-place. For each merge operation that we perform we can keep a count. We can update the interval 2D vector with the optimal intervals that we get instead of using mergeIntervals. Then we can return the interval from interval.begin() to interval.begin() + count - 1. This way the space complexity will further reduce to O(1). Please let me know your views in this appeoach of mine.

[@kirtanprajapati8464]

Your explanation and code are so pretty much. Thanks a lot, bro

[@bhaveshkumar6842]

Your videos are immensely helpful!

[@prateekverma9166]

Your efforts make my struggles easy, awsm content

[@paritoshdadhich2954]

Thank you bhaiya for making such important videos. More power to you!!

[@pratyushgupta319]

I think on Line 5 (09:54) We should first check for null and then .length cause if its null, it will throw NullPointerException... but incase of leetcode they will not give null as an input 😅, they usually give the array of size 0.

[@sumanshekhar8110]

Exactly, that will prevent a null pointer

[@ayushgupta-ds9fg]

Ur explaination are next level

[@pirangitharun8736]

I write my codes in java and I came to know many new things after seeing your code. Thank you bro

[@ishangujarathi10]

Greattt, Understood completely and even coded myself after understanding the logic!!!tysm

[@sush9889]

this course is best ! keep going vikram bhai !

[@-CYSAIANUSHA]

You are awesom.....very crisp but very very effective....can you make a video on how to solve any problem in front of interviewer effectively...?

[@prithvichetty15]

great video please keep making such videos and also please keep providing the solution and code because its great help.

[@aditijain9423]

In the merge step, you also need to check the new pair's 2nd index if it is less than the first pair's 2nd Index, the merge will not be needed since it lies in the first pair.

[@sahilparanjape8602]

end = Math.max(end, i[1]) checks if the 1st pairs second index(end) is greater than the new pair's second index(i[1]).

[@itz_me_imraan02]

Got the optimized solution in my very first attempt 😌

[@boundlesstech5292]

haha 🤣

[@riyadhossain1706]

you're videos are awesome................

[@saifali-fr2zx]

i think we can do this in more efficient way i.e without sorting we follow your 2nd method but without sorting , now we will do same thing again from left to ri8 and then from ri8 to left time complexity will be O(3n)

[@dillirajtimalsina]

no we cant because in arr[] = a b c: if(a and c get's merged but b doen't with both then in either direction it won't merge a and c) lol

[@makelearneasy1050]

actually i have a doubt in line 11 where auto is used then it should start iterating from first pair if interval vector which is same as the pair in mergedIntervals so how after for loop iterator is pointing to second element of array because in next line it is written it[0]

[@bibhasjha3412]

i have same doubt and if u ever found answer to it kindly plz explain

[@innfinityraag7682]

actually it is not pointing to second element of the array it is pointing of the array the point is in first iteration we are comparing if 3 is greater than 1 or not (in first interval) which is true ...then at end of every iteration temp will set to it and it will point to next element so thats how from second iteration temp[1] is 3 and it[0] is 2

[@jatinbhatoya8420]

u are doin a very good job. well done bro

[@kshitijmishra2716]

this is asked today in my interview guys please take this problem seriously

[@TheProblemSolvers38]

Did you answered it .... ?

[@kshitijmishra2716]

@@TheProblemSolvers38 nah i did not solved this problem

[@TheProblemSolvers38]

@@kshitijmishra2716 Sorry to hear that .... But keep striving ... : )

[@infinioda108]

Bro ur interview tips are greeeeatttt :)

[@atulranjan794]

O(nlogn) Time complexity and O(1) space is more efficient vector merge(vector& intervals) { vectorans; sort(intervals.begin(),intervals.end()); ans.push_back(intervals[0]); for(int i=1;i=intervals[i][0]){ int p=ans[ans.size()-1][0]; int q= max(ans[ans.size()-1][1],intervals[i][1]); ans.pop_back(); ans.push_back({p,q}); } else ans.push_back(intervals[i]); } return ans; }

[@atulranjan794]

@takeyouforward

[@Tarun-Mehta]

Keep sharing, Thank you very much 🙏🙏

[@cinime]

Understood! Super awesome explanation as always, thank you very much!!

[@krishnabhardwaj9805]

best solution for this problem...........

[@stith_pragya]

Thank You bro, very well explained>>>>>>>>>>>>>>>>😊😊😊😊😊😊

[@raoshnakquadri8731]

Thank u so much striver for such a nice explanation....

[@harshsheth6633]

This thumbnail is way better but just try to make background light bcoz due to that words are not clear enough...

[@SAKSHIKUMARIP]

thank you for making wonderful content for us!!!

[@notelectrohead]

Python Code: intervals.sort(key=lambda x: x[0]) merged = [] for interval in intervals: # if the list of merged intervals is empty or if the current # interval does not overlap with the previous, simply append it. if(not merged or merged[-1][1] < interval[0]): merged.append(interval) else: # otherwise, there is overlap, so we merge the current and previous # intervals. merged[-1][1] = max(merged[-1][1],interval[1])

[@rajvibagohil6726]

Very good explanation!! Keep it up!!!

[@dadidivya8663]

Why do we need space complexity in the optimised approach.. I think we can avoid it right.. here's my solution class Solution: def merge(self, intervals: List[List[int]]) -> List[List[int]]: intervals=sorted(intervals) i=1 while(i= intervals[i][0]): max1=max(intervals[i][1],intervals[i-1][1]) intervals[i]=[intervals[i-1][0],max1] intervals.remove(intervals[i-1]) else: i+=1 return intervals By the way.. striver.. thank you so so much.. not only for the videos but also the constant motivation... Have started ur sde sheet.. I know its late.. but I am going to do it...Thanks a lot:-)

[@lol2285]

great video , but dont you think you should focus more on explaining how the "merge" works? I mean once someone understand how to merge two arrays ( figuring out what exactly is a merge in this context ), i think they can figure out "which" elements to merge.

[@takeUforward]

I am expecting you to know merge sort

[@lol2285]

@@takeUforward I was pointing to what you were explaining at 4:30, "The merging step", i had a little bit of trouble understand how to code that , Is it a variation of merge sort?

[@_hulk748]

You are great Sir🙏❤✨🙇‍♂

[@Noobgaming-tc1jo]

ary dislike chordo u iz riieeaaal leegend 🚩😁

[@yeswanthh5068]

Thank you understood 🙂🙂💚

[@sumanthakur201]

Please upload more such videos... It's helping. Thank you :)

[@manishmalik.]

You are welcome roll no. 33

[@pawanlok1776]

thank you for making the playlist,, it really helps me a lot..

[@sajramkisho9991]

i have modified the java code.....if anyone feel struck....look below..... class Solution { public int[][] merge(int[][] intervals) { if(intervals.lengthInteger.compare(arr1[0],arr2[0])); Listres=new ArrayList(); int[] current_interval=intervals[0]; res.add(current_interval); for(int[] i:intervals){ int current_begin=current_interval[0]; int current_end=current_interval[1]; int next_begin=i[0]; int next_end=i[1]; if(current_end>=next_begin){ current_interval[1]=Math.max(current_end,next_end) ; } else{ current_interval=i; res.add(current_interval); } } return res.toArray(new int[res.size()][]); } }

[@abhishekk1231]

You're a great teacher!

[@ameyakaranjkar9359]

Wonderful walkthrough brother! The only thing is, I am not able to develop my intuition for why we sort based on start time! 1. What if we sorted based on end time? (Can we develop another algorithm in this case) 2. What if we sorted based on start time but in decreasing order? Can you please throw some light on this as this might help us crack variation problems! Thanks in advance! Love your work. 🙌🙏😊

[@giri1982]

Thanks for the posting!

[@ashishsinha8893]

Love you bro one thing I would like to know everyday you r uploading

[@nikitajaiswal9112]

Wow amazing😍🤩.... Thank you so Much 😊

[@AhmedAdel-xg1cm]

thank you so mush for this amazing explanation, u are my hero :)

[@sonaalmahadani651]

he made it look so easy damm!!!!!

[@hackpiece3094]

Hey Brother! You are doing a great work :) However I would like to point out that the merging result can be put back in the original vector or or data structure. That would make it constant space. ❤️

[@takeUforward]

Not it does not makes it, since you are first taking into some other ds

[@hackpiece3094]

@@takeUforward Brother, will you please have a look on the last implementation of the link? www.geeksforgeeks.org/merging-intervals/amp/

[@sunidhihegde242]

Inside for loop if condition is static rt ?

[@abhinavmishra7617]

Very nicely explained. Thankyou

[@ankitasingh634]

you are a life saver !!

[@classcure9769]

bro i have a nlog(n) binary search solution of this problem(only if given intervals are sorted)........ first make two diff arrays ---start and end where start[i] = Interval[i][0] and end[i] = Interval[i][1] then iterate over end array suppose we are at ith pos then using lower_bound function i can found position in start array which are less the E[i] suppose we get position a then add our first meged interval(which is start[i] , end[a]) into Ans(you can use vector) and then our new position for repeating the same process will be a+1...............................isn't it right aproach(for lower_bound i can also implement it in Log(n) time)................Hoping for a reply

[@jatinkumar4410]

understood....thanks for such nice explanation

[@zishanchaudhary221]

Just Amazing 🥳🥳

[@arvindmaurya7157]

Really helpful for everyone...

[@ESaiCharanKNetha]

This video is helpful, thanks.

[@akanshakedia9933]

Can you explain how arrays.sort(intervals,(a,b)->a[0],b[0]) works?

[@rahul_ji21]

did u get it??

[@soumyabanerjee3886]

this is a lambda expression

[@vasugaur1283]

bro thankyou for making such videos....plz post more videos

[@rajeshagarwal4137]

This question is famous fir JPMC coding round

[@harshitkumarsingh2349]

if your submission on leetcode for this code is only better then 38% coders then try to return intervals if it's size is equal to 1 or 0 you will be better then 99%.

[@takeUforward]

Leetcode runtimes are myth lol

[@100kb3]

currently doing Graphs Series ( new ) Next tree's series, Awesome explanation!

[@apoorvsingh6272]

Great explanation bro

[@tejassrivastava6971]

Thanks for this playlist

[@EdwinaNeheru69]

Thank u bhai...grt work keep going...👌👌👌

[@anuragroshan2195]

THOSE WHO ARE LOOKING FOR SOLUTION WITHOUT USING SORT FUNCTION Here i used a map and TC of code is O(2n) public: vector merge(vector& intervals) { int arr[10000+5]; mapmp; memset(arr,-1,sizeof(arr)); int count=-1; int n=intervals.size(); for(int i=0; imp[intervals[i][0]]){ mp[intervals[i][0]]=intervals[i][1]; } arr[intervals[i][0]]=1; arr[intervals[i][1]]=1; } int num=0; for(int i=0 ; i

[@ECEGrishmaKarekar]

wow thats a good solution

[@acxd]

Understood great explaination!

[@mukulmishra24]

Bro this thumbnail 🤩🤩

[@thisisjustme8149]

Very well understood, thanks a lot!!

[@gopinath7846]

please explain what is time complex and space complex it will be good to understand as well

[@nehasagar9416]

Was waiting for the video

[@936_pratikgupta4]

The code is easy to understand but you will get 2 testcase error due to the first if condition in which the if(intervals.length==0 || intervals.length==null) change it to if(intervals.lenght

[@namanbhardwaj3621]

bhaiya I understood th problem. I liked the old video thumbnail. thanks and keep doing

[@sathyapriyaar1009]

great work!!

[@GrimReaper-gt2xs]

Thank you so much❤️

[@saimahaider1783]

it was really helpful

[@JamWithJingle]

Thanks

[@roushanraj8530]

Big big Thank you bro.......

[@jigyasakodnani3872]

Thanks alot for the video!!

[@DeadPoolx1712]

UNDERSTOOD;

[@satyamsingh_47]

Please help me with the last line of your java code. why can't we simply write return res.toArray() instead of return res.toArray(new int[0][]) ?

[@sksahil1461]

Thank you striver

[@aravindbalaji1503]

Can we change the first condition to intervals.size()

[@rohanthakur9159]

I understood the solution Thanks a lot🥰

[@Yash_Parashar]

Can some give brute force code of this problem??