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 ??
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?
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.
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.
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 ?
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.
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
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.
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.
@@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.
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.
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
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.
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 !!!
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.
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?
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.
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？
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?
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.
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.
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]
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.
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) ....
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
there's not many java creators out there ..you are doing a great job dude ..keep going
agre++
man.. this is crazy, I was stuck in this question today, and you came up with best explanation
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
just finished an interview where this was the question, damn. Wish I saw this sooner... keep doing your thing Nick!
you mind to mention where that interview was?
@@cloud15487 Kargo, a smaller tech company. This is a good interview question though so could show up at any company.
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!
9:16 - "Literally" took me 1 hour to understand from a code from Leetcode.
I'm so glad I found your channel, very helpful to watch.
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 ??
Thanks Nick. This was very helpful.Please do similar popular quesitions
You can improve the run time if the you use arr1[0] - arr2[0] instead of compare while sorting. BTW the explanation was great
You are amazing brother, your coding style and explanation is pretty simple.
Best explanation I have ever come across for this question🎉
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?
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.
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.
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 ?
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.
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
More power to you,I would request everyone to support this guy.
I think the best explanation u have ever given in your videos
may be i had understood in first attempt
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.
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.
@@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.
Hi Nick.. Can you make a video on "How the Comparator does the sorting stuffs internally" ??
what if we do boom boom boom in interview just like u did @7:33
Thank you, I was totally stuck even didn't understand the question but u helped me nice explanation.
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.
Thank you so much Nick.
God Bless Everyone😇
Thank You So Much for this wonderful video........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
I spent a few hours yesterday night and solved it by myself
Great stuff! love the authenticity in you
Thank you, I am coding in javascript and this helped.
Long live Nick White.. thanks man
Thank you, my friend. I appreciate your work very much. Keep it up! God bless you.
how are you updating list with the current intervals end directly
can you pleas explain it in detail please ??
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
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.
What is the time and space complexity of your solution in the video?
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 !!!
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.
@@nishantsabharwal13 thanks 🙂
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?
well, this is exactly what I'm confused with too ... could you understand it?
exactly same doubt. found ans?
Guys found the answer ??
Would this work with straddling intervals?
E.g. [3,4], [1,5]
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.
he sorts the array by first element and then he uses Math.max(..) to choose 5 instead of 4 (in your example)
0:06, best part of the video hahaha
Whats the time and space complexity :-O(n) ?
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？
can we use for loop with an index, for ( int i = 0 ; i < intervals.length; i++ ) ? thanks
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?
Very helpful,thank you dude!
great man. keep it up, 1 like from india
Was asked similar problem in Uber 1st round, this is like OR one more was AND the intervals of 2 2D arrays
Is there a faster way to do this? I got a bad runtime score.
the best explanation ever thanks man
Thanks. LC 76 video whenever you get time.
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
I have the same question .
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.
Thank you very much Nick
what does (arr1,arr2) -> Integer.compare(arr[0],arr[1]); do
Sort according to the first digit in the arrays
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.
feel u bro!!
Hey Nick, can you do a video on 986. Interval List Intersections?
can someone explain why in the return statement the array is left blank. new int[output_arr.sizeOf()] [ ])l
I think second [ ] is for collumn as return type is int[ ][ ]
This is really great explanation. Can you please explain the complexity also. It will be of great help.
T.C : NlogN + N
S.C : N
unable to understand return output_arr.toArray(new int[output_arr.size()][]);
Is there a linear solution?
# 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
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]
nah it is not
Very well explained.
What's the time complexity
great explanation!!
Great explanation. Thanks sir.
big thank you from UB ;)
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.
10:12 💀
VERY HELPFUL! Thanks
Thanks for watching!
I WAS SO FUCKING CONFUSED BRO I THOUGHT WHY WAS HE OPERATING IN THE 2D ARRAY OMG
I don't get the comparator part
Crystal clean. Thanks
I hate when he says "ITS A PRETTY EASY PROBLEM"
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
Please explain Super Washing Machines of Leetcode.
What does this ' -->' mean?
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) ....
Do you normally redo the entire video if you mess up?
wow, great solution.
Thanks man!
Can u slove hacker earth challenges
Thank you! I got unstuck
thank you sooooo much
You should have showed how to do this with interval trees. The sorting method is trivial.
thanks
thank u so much
Learn case convention in Java first. Then got to algos :-)
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
Awesome
Thanxxxxxx
dude
I came here looking for a linear solution :(
I'm so glad I found your channel, very helpful to watch.