LeetCode 56. Merge Intervals (Algorithm Explained)

The Best Place To Learn Anything Coding Related - bit.ly/3MFZLIZ
Join my free exclusive community built to empower programmers! - www.skool.com/software-develo...
Preparing For Your Coding Interviews? Use These Resources
--------------------
(My Course) Data Structures & Algorithms for Coding Interviews - thedailybyte.dev/courses/nick
AlgoCademy - algocademy.com/?referral=nick...
Daily Coding Interview Questions - bit.ly/3xw1Sqz
10% Off Of The Best Web Hosting! - hostinger.com/nickwhite
Follow Me on X/Twitter - x.com/nickwhitereal
Follow My Instagram - / nickwwhite
Other Social Media
----------------------------------------------
Discord - / discord
Twitch - / nickwhitettv
TikTok - / nickwhitetiktok
LinkedIn - / nicholas-w-white
Show Support
------------------------------------------------------------------------------
Patreon - / nick_white
PayPal - paypal.me/nickwwhite?locale.x...
Become A Member - / @nickwhite
#coding #programming #softwareengineering

[@adarshmishra4431]

there's not many java creators out there ..you are doing a great job dude ..keep going

[@preetkatiyar969]

agre++

[@ianchui]

I'm so glad I found your channel, very helpful to watch. I always add your videos to my watch later, then just watch when I'm on the bus

[@xnl3358]

man.. this is crazy, I was stuck in this question today, and you came up with best explanation

[@shubhamchourasia2265]

9:16 - "Literally" took me 1 hour to understand from a code from Leetcode.

[@depshallburn]

It makes sense once you realize updating the last index of current_interval (line 20), also updates it in the ArrayList. Thanks so much for this!

[@mangeshkumargabhane4671]

I'm so glad I found your channel, very helpful to watch.

[@darrenwang7613]

just finished an interview where this was the question, damn. Wish I saw this sooner... keep doing your thing Nick!

[@cloud5887]

you mind to mention where that interview was?

[@darrenwang7613]

@@cloud5887 Kargo, a smaller tech company. This is a good interview question though so could show up at any company.

[@pradip318]

You are amazing brother, your coding style and explanation is pretty simple.

[@anoopm3605]

Thanks Nick. This was very helpful.Please do similar popular quesitions

[@yassineattia3009]

Great stuff! love the authenticity in you

[@parassaini9010]

Thank you, I was totally stuck even didn't understand the question but u helped me nice explanation.

[@vikramchaudhary440]

More power to you,I would request everyone to support this guy.

[@surajgrandhi6742]

I think the best explanation u have ever given in your videos may be i had understood in first attempt

[@priyamshah7117]

In which step are we updating the (second no of interval). after encountering an overlap, we do find largest of two curr_end and next_end, but before only we added it to output_arr. so we do need to update [1, 3] to [1, 6]. Where are we doing that.

[@felixrajkumar3177]

You can improve the run time if the you use arr1[0] - arr2[0] instead of compare while sorting. BTW the explanation was great

[@julietgeorge4858]

Thank you, I am coding in javascript and this helped.

[@akashbharatwaj6945]

Hi Nick.. Can you make a video on "How the Comparator does the sorting stuffs internally" ??

[@renjieyu8700]

Very helpful,thank you dude!

[@maksymr.7191]

Thank you, my friend. I appreciate your work very much. Keep it up! God bless you.

[@shusenacademy]

can we use for loop with an index, for ( int i = 0 ; i < intervals.length; i++ ) ? thanks

[@hacker-7214]

The idea u take the current interval initially and add it into the list is genius and updating it. Like eventho for loops r easy. I find it hard to even code loops cuz u want the same thing to happen in loops but i always mess up.

[@hacker-7214]

@@bilaltariq7819 thank you youre a genius! Enevn tho this concept seems obvious idk why i didnt see the importance of it. I need to practice finding out the loop invariant everytime i encounter a problem that requires a loop.

[@jerrywu751]

what if when the for loop runs into the last interval the (current_end > next_begin) is True and therefore it doesn't put the current array into the output_arr?

[@sabreenkaur7349]

What is the time and space complexity of your solution in the video?

[@sakshiaggarwal6199]

Thank you so much Nick. God Bless Everyone😇

[@aravindhsaairavichandran8404]

Long live Nick White.. thanks man

[@aligohar1708]

6:32 I am a little confused because you just initialized an int as an int* and there was no error, i mean intervals was a 2d array... One of which array was containing only pointers and you initialized that pointer to an int ??

[@devyashb]

the best explanation ever thanks man

[@stith_pragya]

Thank You So Much for this wonderful video........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@cryptojeff3993]

Crystal clean. Thanks

[@TheIntraFerox]

I’m stuck on something. How does current_interval[1] = Math.max(current_end, next_end) in the loop cause a change in the arrayList? If it is because we pass by reference then why was there not change in current_interval in the array list when we did current_interval = interval?

[@prakanshmishra9004]

So, current_interval is pointing to the first element of output_arr when "current_interval[1] = Math.max(current_end, next_end)" is done. So, it changes the end point of the first array. But current_interval changes to point to the new interval when "current_interval = interval" is done. So, current_interval acts as just the pointer for the different arrays in the list at different points. But the actual arrays in the list remain the same. This is because list is not stored contiguously but it is just a chain of elements pointing to the next one.

[@Will-en6gw]

Yeah I was stuck on this too but what Prakansh said makes sense, current_interval is pointing to the first element in the output list because we just got done adding it. Then when doing current_interval[1] = Math.max(current_end, next_end) we are directly accessing a primitive data type, which we can directly mutate. This is why it gets changed in the output list, because it is a primitive data type. Then when we do current_interval = interval, we are telling the compiler to point to interval because arrays are reference data types, not primitives.

[@anirbandey303]

Great explanation. Thanks sir.

[@dheerajkumark7165]

great explanation!!

[@farzanatasnim7339]

Thanks man!

[@rohitparthasarathy6671]

Very well explained.

[@jyothisejohny]

I have a doubt here . After storing the 1st interval in "current_interval", which is ([1, 3]) in this case, you start iterating through the intervals . When you do that it should always start from the 1st interval ([1, 3]). Then how's it pointing to the 2nd interval ([2, 6]) during the 1st iteration? It's like comparing the same element with itself .Can someone explain ?

[@Dragonblade1453]

I was stuck on too but if you merge [1,3] with [1,3] you get [1,3] since the Math.max(current_end, next_end) is basically Math.max(3,3). So first iteration compares itself and creates a clone.

[@rodanm]

0:06, best part of the video hahaha

[@nribackpacker]

what if we do boom boom boom in interview just like u did @7:33

[@jamjam3448]

I spent a few hours yesterday night and solved it by myself

[@nikhilv6]

Was asked similar problem in Uber 1st round, this is like OR one more was AND the intervals of 2 2D arrays

[@yuchenguo9108]

Hey Nick, can you do a video on 986. Interval List Intersections?

[@sidhartheleswarapu]

Is there a faster way to do this? I got a bad runtime score.

[@johnnywilson3071]

I got a method which is faster but uses a little more memory. What I did was initialize two variables called which are set as intervals[0][0] and intervals[0][1]. Then I make a third variable in a for loop which is set to intervals[i][0] which compares its value to the upper interval, if its lower, the upper interval is modified if interval[i][1] is higher than the current upper interval. If intervals[i][0] is higher than the lower and upper bound are pushed to a 2nd array and new bounds, intervals[i][0] (lower) and intervals[i][1] (higher) are created. Keep doing this until the for loop ends after which we push the final values of "c_val" and "bound" as an array to our 2nd vector and return that vector. You'll need to sort intervals first before assigning the variables.

[@thechhavibansal]

VERY HELPFUL! Thanks

[@NickWhite]

Thanks for watching!

[@devanshikhare1342]

Just a question if anyone could tell: current_interval=interval[0] and when we iterate : for(int[ ] interval : intervals) so where does it starts from .................interval=intervals[0] ? is it so if it is so, we check same elements both pointing to intervals[0] ? thanks . PLease help !!!

[@nishantsabharwal13]

That's correct, we check the first element by itself change it to the same element going in the if condition and not really adding it again. We could have just used a for loop starting from the index 1 instead, that would have been a bit more clear.

[@devanshikhare1342]

@@nishantsabharwal13 thanks 🙂

[@doomhead9109]

thank you sooooo much

[@prachisharma7500]

Whats the time and space complexity :-O(n) ?

[@iamnoob7593]

1. if(intervals.lengtharr1[0]-arr2[0]); 5 List l =new ArrayList(); 6 int[] current; 7 current = intervals[0]; 8 l.add(current); 9 for(int[] interval:intervals){ 10 int cbegin = current[0]; 11 int cend = current[1]; 12 int nbegin = interval[0]; 13 int nend = interval[1]; 14 if(cend>=nbegin){ 15 current[1] = Math.max(cend,nend); 16 } 17 else{ 18 current = interval; 19 l.add(current); 20 } 21 } return l.toArray(new int[l.size()][]); Could u pls xplain line no 18 current is pass by reference ,changes is done automatically to list,but at line 18 current=interval ,so previous current in list is *LOST*,because list stores reference of current

[@rushabhjaiswal1442]

how are you updating list with the current intervals end directly can you pleas explain it in detail please ??

[@leroyhutchinson4497]

I think he is not copying the array, he is setting a reference to it, so I guess that makes it possible to directly change the value in the arraylist, in the else statement it looks like he changes the reference and cuts off that connection

[@HaruharaxX]

So he's able to do that because ArrayList is mutable in Java. Whatever modification he performs on the current interval within the for loop is also reflected inside the interval found in output_arr. If he were to update the interval under a new variable assignment, then the interval update wouldn't roll over to the interval found in output_arr. This same reasoning is also applicable to Python.

[@ihopethiscommentisntabusiv4670]

Is there a linear solution?

[@HiBMlive]

Thanks. LC 76 video whenever you get time.

[@chelseaip759]

What's the time complexity

[@adarshupadhyay8265]

unable to understand return output_arr.toArray(new int[output_arr.size()][]);

[@user-we9rm1rm5u]

According to example 1, this statement int[] cur_interval=intervals[0]; output_arr.add(cur_interval); has put [1,3] into the answer array. Aren't you wrong？

[@deluluvish]

thank u so much

[@debanjanasantra6724]

Thanks Nick! V helpful :) Can someone help me understand how come if I change any value of current_interval, then it automatically updates in the output_arr list? Is it because of pass by reference nature of Java?

[@ananthr1583]

well, this is exactly what I'm confused with too ... could you understand it?

[@priyamshah7117]

exactly same doubt. found ans?

[@mrunald7305]

Guys found the answer ??

[@patagoniachief5973]

big thank you from UB ;)

[@yazicib1]

Would this work with straddling intervals? E.g. [3,4], [1,5]

[@pulkitindora]

Yeah it will, that's why he sorted the array in the first place. If the intervals are sorted based on their first indexes, we can easily merge them using this algo.

[@daniellee9825]

he sorts the array by first element and then he uses Math.max(..) to choose 5 instead of 4 (in your example)

[@manjushajagtap3718]

This is really great explanation. Can you please explain the complexity also. It will be of great help.

[@Harsh-di5rl]

T.C : NlogN + N S.C : N

[@razorhxh7371]

can someone explain why in the return statement the array is left blank. new int[output_arr.sizeOf()] [ ])l

[@devanshikhare1342]

I think second [ ] is for collumn as return type is int[ ][ ]

[@palak2708]

wow, great solution.

[@amitnain8489]

great man. keep it up, 1 like from india

[@sagargada73]

what does (arr1,arr2) -> Integer.compare(arr[0],arr[1]); do

[@hamsithachallagundla]

Sort according to the first digit in the arrays

[@piyushgupta2325]

I don't get the comparator part

[@akd070]

How is modifying the current_interval[1] modifying the value in the output_arr . Sorry if it is a stupid question , learning DS from the start

[@mysterygirl191]

I have the same question .

[@zCynicaI]

ArrayLists are mutable in java, That means you can change the value at any point of time, So he just goes ahead and updates the value and it reflects in the output array too.

[@ManpreetSingh-tf5ef]

thanks

[@venpro8705]

Can u slove hacker earth challenges

[@HarshGangwar]

Please explain Super Washing Machines of Leetcode.

[@priyankareddy7408]

Thank you! I got unstuck

[@piyushgupta2325]

I WAS SO FUCKING CONFUSED BRO I THOUGHT WHY WAS HE OPERATING IN THE 2D ARRAY OMG

[@infinteuniverse]

Who comes up with these answers in 45 min during a coding assessment from only seeing this the first time?? I just finished a similar question 'insert intervals.' It took me so long to do, but I did it without looking for help. It feels like I'll never pass those coding interviews.

[@keshavgupta2647]

feel u bro!!

[@jugsma6676]

Wouldn't this be the easiest way to do? def merge_itervals(intervals): last_interval_val = intervals[0][0]-1 for i, interval in enumerate(intervals): if interval[0]

[@legendnvfade6375]

nah it is not

[@akhilguptavibrantjava]

Awesome

[@sidn515]

This way of coding might help you clear the interviews, but is highly discouraged in practice since the leaky side effects are impossible to track in enterprise level projects.

[@Vishal-ki2df]

What does this ' -->' mean?

[@TheSuper10dulkar]

it refers to the lambdas .. snippet example : int compare(Int h1, Int h2) { return h1.compareTo(h2); } is replaced here as (h1,h2)--> h.compareTo(h2) ....

[@shantanuneema]

Why can't we simply do this instead (python): def merge(self, intervals: List[List[int]]) -> List[List[int]]: if len(intervals) = intervals[i][0]: result[count][1] = max(intervals[i][1], result[count][1]) else: result.append(intervals[i]) count += 1 return result

[@kose241]

Do you normally redo the entire video if you mess up?

[@andychang1179]

Thanxxxxxx

[@mananpatel884]

# python intervals = [[1,3],[6,9]] newInterval = [2,5] intervals.append(newInterval) intervals.sort() final_list = [] current_interval = intervals[0] # print current_interval[0] final_list.append(current_interval) for interval in intervals: current_begin = current_interval[0] current_end = current_interval[1] next_begin = interval[0] next_end = interval[1] if current_end >= next_begin: current_interval[1] = max(current_end,next_end) else: current_interval = interval final_list.append(current_interval) print final_list

[@LUCIFER-lw4rc]

10:12 💀

[@miteshkumar3183]

You should have showed how to do this with interval trees. The sorting method is trivial.

[@Steklopod]

Learn case convention in Java first. Then got to algos :-)

[@SHSelect]

I hate when he says "ITS A PRETTY EASY PROBLEM"

[@sebastianbaptiste4905]

dude

[@codedoctor3265]

class Solution: def merge(self, intervals): 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]) return merged

[@TheJuancar0000]

I came here looking for a linear solution :(

[@karana2260]

I'm so glad I found your channel, very helpful to watch.