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.
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 ??
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.
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
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.
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.
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.
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？
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.
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?
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.
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.
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]
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.
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) ....
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.
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++
9:16 - "Literally" took me 1 hour to understand from a code from Leetcode.
man.. this is crazy, I was stuck in this question today, and you came up with best explanation
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!
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.
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 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
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.
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.
You can improve the run time if the you use arr1[0] - arr2[0] instead of compare while sorting. BTW the explanation was great
what if we do boom boom boom in interview just like u did @7:33
Hi Nick.. Can you make a video on "How the Comparator does the sorting stuffs internally" ??
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
Best explanation I have ever come across for this question🎉
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.
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.
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 🙂
Is there a faster way to do this? I got a bad runtime score.
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？
Whats the time and space complexity :-O(n) ?
Thanks Nick. This was very helpful.Please do similar popular quesitions
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.
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 ??
Thank You So Much for this wonderful video........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
What is the time and space complexity of your solution in the video?
More power to you,I would request everyone to support this guy.
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?
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.
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)
I spent a few hours yesterday night and solved it by myself
can we use for loop with an index, for ( int i = 0 ; i < intervals.length; i++ ) ? thanks
You are amazing brother, your coding style and explanation is pretty simple.
I think the best explanation u have ever given in your videos
may be i had understood in first attempt
unable to understand return output_arr.toArray(new int[output_arr.size()][]);
I'm so glad I found your channel, very helpful to watch.
Is there a linear solution?
0:06, best part of the video hahaha
I don't get the comparator part
What's the time complexity
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[ ][ ]
what does (arr1,arr2) -> Integer.compare(arr[0],arr[1]); do
Sort according to the first digit in the arrays
Thank you, I was totally stuck even didn't understand the question but u helped me nice explanation.
Was asked similar problem in Uber 1st round, this is like OR one more was AND the intervals of 2 2D arrays
I hate when he says "ITS A PRETTY EASY PROBLEM"
10:12 💀
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
Great stuff! love the authenticity in you
Long live Nick White.. thanks man
Hey Nick, can you do a video on 986. Interval List Intersections?
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!!
Thank you so much Nick.
God Bless Everyone😇
Thank you, I am coding in javascript and this helped.
Thanks. LC 76 video whenever you get time.
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
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) ....
# 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
Very helpful,thank you dude!
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
Very well explained.
Thank you, my friend. I appreciate your work very much. Keep it up! God bless you.
I WAS SO FUCKING CONFUSED BRO I THOUGHT WHY WAS HE OPERATING IN THE 2D ARRAY OMG
Do you normally redo the entire video if you mess up?
Please explain Super Washing Machines of Leetcode.
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.
Can u slove hacker earth challenges
the best explanation ever thanks man
great explanation!!
great man. keep it up, 1 like from india
Great explanation. Thanks sir.
Thank you! I got unstuck
big thank you from UB ;)
VERY HELPFUL! Thanks
Thanks for watching!
Thanks man!
Crystal clean. Thanks
wow, great solution.
Learn case convention in Java first. Then got to algos :-)
thanks
You should have showed how to do this with interval trees. The sorting method is trivial.
thank you sooooo much
thank u so much
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
Thanxxxxxx
Awesome
dude
I came here looking for a linear solution :(
I'm so glad I found your channel, very helpful to watch.