Merge Intervals - Sorting - Leetcode 56

[@vishnuv.7807]

I just started the LeetCode grind and this was my first medium problem I had attempted. Your explanation was crazy clear and it really helped me learn how this algorithm works.

[@NeetCode]

I'm happy it was helpful 🙂

[@II_superluminal_II]

man out of all the other over zealous ones, you are one of the most humble and creative teacher I have met. I hope you know you are helping alot of people who are good coders not confident with interviewing help ease a little tension.

[@srinadhp]

Thank you so much! I complicated the solution way too much.. but when I look at yours, I now understand what I missed. Your explanation as usual, helped a great deal. Thank you so much!

[@licokr]

Thank you ver ymuch, NeetCode. Not only drawing, your explanation and code is very straight-forward and easy understand. I'm really glad I found out your channel!

[@hwang1607]

just using intervals = sorted(intervals) works as well

[@ShivamSharma-t8c]

affects space complexity as it creates new object, but good option for a beginner tho

[@yilinliu2238]

thank god whenever you have a video on the lc I am doing

[@t-distributedkid3825]

This is my first medium problem like many others Explanation was great... On point

[@dominic_lee]

this is a really good problem。it is a bit tricky but you can learn a lot

[@rahulshah6119]

great video again! btw you don't need a custom lambda key comparator, python sorts by the first element by default anyways so `intervals.sort()` would work as well for line 4.

[@husainshaikh1433]

Explicit is better than implicit

[@marcelofernandes3230]

@@husainshaikh1433 Yeah, but I mean this is a feature of the language one should be aware for these interview questions. It's really useful for defining tiebreakers in heaps, for instance.

[@neon13x]

If the first element is same python will compare the second element and so on, by passing a key function it will not check the rest of the values if key is same.

[@cathyhuang8557]

Good explanation~ Do you have a patreon? I would like to buy you a coffee to support your hard work! Keep working!

[@NeetCode]

Thank you, that means a lot! If you would like to support on patreon here is the link: www.patreon.com/NEETcode (completely optional, teaching is already rewarding for me =) )

[@nuamaaniqbal6373]

Your solutions are very intuitive and clean!

[@KrishnaKumar-jz7zu]

Thank you very much, your way of approching problem and explanation makes difficult level problem easy for me !

[@Sportamrina]

Thanks!

[@NeetCode]

Thank you so much!

[@snake1625b]

The only video that helped me with this question. Thanks

[@Cruzylife]

gonna continue on this problem tomorrow. Your explanations are better than grokking's. Using your videos and Grokking is the ultimate combination that is helping me so much rn

[@PippyPappyPatterson]

Can you post a link to Grokking's channel? I searched "Grokking merge intervals" but didn't find anything. Or is it in a different medium?

[@franklinmaradiaga2401]

@@PippyPappyPatterson I think CruzyLife was referring to Grokking the Coding Interview, which is a course to learn patterns for technical interviews

[@PippyPappyPatterson]

@@franklinmaradiaga2401 Thanks

[@shantanukumar4081]

You made it easy. Great Explanation !!!

[@pa114able]

Great explanation buddy! I was looking for implementation in Python and you described it perfectly!

[@jackieli1724]

thank u very much😭the best leetcode video in youtube!

[@ishxnnn]

I love you Neetcode, you're my leetcode buddy

[@adolfoestebanfragosomagall7975]

Great explanation, thank you!. It would be a good idea to also explain the O(n2) solution using connected components and then derive the optimal solution.

[@DeGoya]

I actually had the idea of sorting them first, but I though there must be a better solution, since that would be too easy

[@anshitasaxena3992]

I wrote this way: def merge(self, intervals: List[List[int]]) -> List[List[int]]: i = 0 finalList = [] intervals.sort(key = lambda i: i[0]) while i < len(intervals): start = intervals[i][0] end = intervals[i][-1] while i+1 < len(intervals) and end >= intervals[i+1][0]: i+=1 end = max(end, intervals[i][-1]) finalList.append([start, end]) i += 1 return finalList

[@zarynooi5669]

you are a life saver

[@radelfalcao9327]

very clear explanation

[@ruiliang6819]

Good vid, keep the good work up!

[@kma1138]

Learning python + leetcoding is sick

[@aniruddhmukeshiiitdharwad7596]

love your channel man !! youre doing lovely work ! love from india!

[@anonymoussloth6687]

Sometimes, we have to sort the intervals based on the end time like in activity selection problem. So when do we choose which?

[@josecabrera7947]

Dude you are the best !!! I honestly attribute my near mastery of python and ability to solve leetcodes to you hahah. Youve taught me so much bro and for that i want to say thank you (:

[@NeetCode]

Glad I could be helpful 🙂

[@JamesBond-mq7pd]

super efficient way. impressive. unreal. wow.

[@sun-ship]

thank you so much for your work!!

[@douglaswong6560]

clean and concise, thank you!

[@venkateshv626]

Very nice explanation

[@harikuduva]

Can you answer the follow up of doing it from a stream opposed to a list?

[@asdfasyakitori8514]

Great video!

[@yashpathak9285]

Sometimes coding in Python feels like cheating!!

[@mariambhatti8515]

This guy must be given a nobel prize by leetcode :)

[@jackfilleyreviews4030]

brooo i love you

[@littlelittlebing]

if the interval length is 1, is interval [1:] out of index?

[@YN-jz2kp]

Nicely explained

[@nathamuni9435]

One small qustion that since we sort the end ...why cant we pick the next value which will definitely be grater⁉❔

[@raishamonga4364]

we only sorted from the start values, not from the ending values so for all we know the ending value of the next interval could actually be smaller than the ending value of the current interval. [1,23], [5,18] => the intervals are sorted form index 0 (or the starting value) and must be merged but if we merge them and make the merged interval [1,18] we just made the interval smaller so our final output would not be right

[@jyotioh3723]

sorta hilarious how elegant these solutions look compared to what I tried to cook up looking at the problem =[

[@xx133]

Can’t this be done in place by using range instead?

[@yogeshk8323]

how you are handling empty list here

[@ilanaizelman3993]

Amazing. Thx!

[@TheStefanV]

public int[][] merge(int[][] intervals) { Arrays.sort(intervals,(a,b)->a[0]-b[0]); List mergedIntervals = new ArrayList(); int[] current = intervals[0]; int[] next = new int[2]; for (int i = 0; i < intervals.length; i++) { next = i < intervals.length -1 ? intervals[i+1] : next; // pointer has reached end, cannot have a 'next' array if ( current[1] >= next[0] && i < intervals.length - 1) { // currentHi > nextLo // currentHi is now the max of currentHi and nextHi, continue onto next iteration and keep trying to merge more current[1] = Math.max(next[1], current[1]); } else { mergedIntervals.add(current); // cannot merge an interval, must add interval as is current = next; } } return mergedIntervals.toArray(new int[0][]); // convert to array }

[@seenumadhavan4451]

Learn python 😂

[@דניאלאביב-ו6ת]

why sorting by start is working, and by end isn't?

[@joyceawesome1705]

Great explanation and very simplified solution. I tried out the code and it failed on this test case: [[1,4],[0,4]]. The output is supposed to be [0, 4], instead I got [1, 4]

[@joyceawesome1705]

Nevermind. I found that my error came from initializing the output array before sorting the intervals.Thanks so much for this video.

[@ruspatel1996]

Isn't using a slice instead of range slower?

[@chair_smesh]

It creates extra memory right?

[@ruspatel1996]

@@chair_smesh Yes specifically O(k) space and it also takes O(k) time to copy the elements.

[@sundararamanp]

i always have the doubt. is it okay to use ready made functions like sort and lambda in ds algo interview round

[@bharanidharan.m4245]

Yes, because there is limited time to deal a problem and sorting is basic to everyone

[@whonayem01]

Thanks

[@qingyachen1635]

Great!!!

[@Historyiswatching]

Gah I feel so dumb, these medium problems are hard. Maybe I should stick with easy ones ... if mediums are too hard? Right?

[@manojk1494]

Could anyone please help me on this...? def merge(intervals: List[List[int]]) -> List[List[int]]: ~~~~^^^^^ TypeError: list indices must be integers or slices, not type Process finished with exit code 1

[@thecustompropper1279]

what if one of the intervals completely lie inside another interval

[@rickhouseshorts]

I tweaked the algorithm by starting with a blank list for output and using a while i < sortedList.size and running DFS on each interval -> getAllValuesWithinRange(newInterval, previousInterval, index), then recursing and updating index (index + 1) IF currentStartingPoint

[@dingus2332]

Basically you took a minHeap and Stack to solve this

[@johnwick2018]

My solution: probably O(n^2) I have no idea how it works but here it is, after 4 hours and 12 attempts import numpy as np from typing import List class Solution: def merge(self, intervals: List[List[int]]) -> List[List[int]]: n = max(intervals, key=lambda x: x[1])[1] temp = np.zeros(n + 1, np.uint8) for l, r in intervals: if l < r: if (temp[l] == 0 or temp[l] == 3) and (temp[r] == 0 or temp[r] == 3): temp[l] = 2 temp[r] = 2 temp[l + 1: r] = 1 elif temp[l] == 2 and temp[r] == 2: if np.count_nonzero(temp[:l + 1] == 2) & 1: temp[l] = 2 else: temp[l] = 1 if np.count_nonzero(temp[r:] == 2) & 1: temp[r] = 2 else: temp[r] = 1 temp[l + 1: r] = 1 elif temp[l] == 2 and temp[r] == 1: if np.count_nonzero(temp[:l + 1] == 2) & 1: temp[l] = 2 else: temp[l] = 1 temp[l + 1: r] = 1 elif temp[l] == 2 and (temp[r] == 0 or temp[r] == 3): temp[r] = 2 if np.count_nonzero(temp[: l + 1] == 2) & 1: temp[l] = 2 else: temp[l] = 1 temp[l + 1: r] = 1 elif (temp[l] == 0 or temp[l] == 3) and temp[r] == 2: temp[l] = 2 if np.count_nonzero(temp[r: n + 1] == 2) & 1: temp[r] = 2 else: temp[r] = 1 temp[l + 1: r] = 1 elif temp[l] == 1 and temp[r] == 2: if np.count_nonzero(temp[r: n + 1] == 2) & 1: temp[r] = 2 else: temp[r] = 1 temp[l + 1: r] = 1 elif temp[l] == 1 and (temp[r] == 0 or temp[r] == 3): temp[r] = 2 temp[l + 1: r] = 1 elif temp[l] == 1 and temp[r] == 1: temp[l + 1: r] = 1 elif (temp[l] == 0 or temp[l] == 3) and temp[r] == 1: temp[l] = 2 temp[l + 1: r] = 1 else: # l == r if temp[l] == 0: temp[r] = 3 i = 0 flag_left = False num_left = None ans = [] while i < n + 1: if temp[i] == 2 and not flag_left: flag_left = True num_left = i elif temp[i] == 2 and flag_left: ans.append([num_left, i]) flag_left = False num_left = None elif temp[i] == 3: ans.append([i, i]) i += 1 return ans

[@nikhil_a01]

That is one of the craziest solutions I've ever seen anyone post. Either on KZbin or in the LeetCode forums. But props to you for sticking with it. I don't think enough people are willing to try really hard. Everyone's in a rush for interview prep and wants to look up the solution after 20 minutes.

[@howitfeelslike5381]

really nice dude ! huge respect for not giving up

[@DanielRodrigues-bx6lr]

jesus lol You even used numpy How long did it take you from start to end (pun intended)?

[@BioInASec]

I can not seem to implement a solution myself 😒😒

[@janardannn]

i could do it, but with worse time complexity, recursive n^2 log n

[@s49243]

public int[][] merge(int[][] intervals) { Arrays.sort(intervals, Comparator.comparingInt(a -> a[0])); ArrayList output = new ArrayList(); output.add(intervals[0]); int index=0; for (int i = 1; i < intervals.length; i++) { int start = intervals[i][0]; int end = intervals[i][1]; int lastend = output.get(index)[1]; if (start

[@edwardteach2]

U a God

[@nathamuni9435]

like meeting room.......

[@tefradc]

can you code using c++,that will be very helpful:)

[@CostaKazistov]

class Solution { public: vector merge(vector& intervals) { sort(intervals.begin(), intervals.end(), less()); vector res; res.push_back(intervals.front()); for (int i = 1; i < intervals.size(); ++i) { int start = intervals[i][0]; int end = intervals[i][1]; int lastEnd = res.back().back(); if (start

[@jamalyarfoor5798]

I got 6000ms solution

[@andrewsucks7645]

you did not cover edgecases like this [[1,4],[0,4]]

[@NeetCode]

If we sort based on start time I don't believe we have to worry about this one