I come to your solutions first for new Leetcode problems. Sometimes I think, "wow there's got to be a more elegant way to do this." Then I look at the 🐍 solutions on Leetcode discussions and I realize how yours blows everything else out of the water. The best part of following along with your solutions is I find myself thinking through algorithms similar to you. It's like being in the lectures of a great math professor and assimilating their thought processes into my repertoire.
seriously... a lot of the LC discussion Python solutions are these dumb one-liners that miss the point about writing readable code in interviews Neetcode is top notch
@@roywastaken I've been working with some people that do more declarative programming via the `itertools` module (e.g. `zip`, `map`, `filter`, unpack operator `*`). I _do_ totally agree that the one-liners are impossible to read for anyone beside the author. _BUT_ , after I sat down and took the time to understand iterables, their iterators, and the basic `itertools`, implementing some idioms in single lines can compress the mental overhead of some leetcode solutions as I study them- even if I would expand them back out in an interview setting for legibility.
pretty smart solution, i feel like its difficult to come up with in an interview, heres the commented code if it helps anyone: class Solution: def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]: res = []
for i in range(len(intervals)): if newInterval[1] < intervals[i][0]: # Right bound of of new interval is to the left of current interval res.append(newInterval) return res + intervals[i:] elif newInterval[0] > intervals[i][1]: # Left bound of new interval is to the right of current interval res.append(intervals[i]) else: # Some part of the the new interval is overlapping with the current interval newInterval = [min(newInterval[0], intervals[i][0]), max(newInterval[1], intervals[i][1])] res.append(newInterval) return res
Your solution is so compact and clean, mine had 2 separate while loops, then a for loop to get the answer, this is way cleaner and better. This also opened my mind to how to think about this problem more logically. Thank you! Liked!
You could do this and avoid returning twice res = [] i, n = 0, len(intervals) while i < n: if newInterval[1] < intervals[i][0]: break elif newInterval[0] > intervals[i][1]: res.append(intervals[i]) else: newInterval = [min(newInterval[0],intervals[i][0]),max(newInterval[1],intervals[i][1])] i+=1 res.append(newInterval) return res + intervals[i:]
now it is a must after solving problems, watching your explanation. this is absoultely amazing. i didn't think of expanding the new interval array so i had to make a lot of cases and plus, conditions you wrote look amazingly easy. knowing well what exactly you have to do. thanks a lot. i learned a lot today too
Stack Solution Different Perspective class Solution: def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]: # Time: O(n) # Space: O(n) res = [newInterval] for n in intervals: start, end = n iStart, iEnd = res.pop() # Compressing from Left Side if start = iStart : res.append([start, max(iEnd, end)]) # Compressing from Right Side elif iStart = start : res.append([iStart, max(iEnd, end)]) #Inserting in Ascending Order with No Compression elif start < iStart: res.append([start, end]) res.append([iStart, iEnd]) else: res.append([iStart, iEnd]) res.append([start, end]) return res
from typing import List class Solution: def insert( self, intervals: List[List[int]], newInterval: List[int] ) -> List[List[int]]: res = [] added = False for i in range(len(intervals)): if newInterval[1] < intervals[i][0]: res.append(newInterval) res += intervals[i:] added = True break elif newInterval[0] > intervals[i][1]: res.append(intervals[i]) else: newInterval = [ min(newInterval[0], intervals[i][0]), max(newInterval[1], intervals[i][1]), ] if not added: res.append(newInterval) return res
Cleaner Solution from LC: class Solution: def insert( self, intervals: List[List[int]], new_interval: List[int] ) -> List[List[int]]: total_intervals = len(intervals) index = 0 merged_intervals = [] # Case 1: No overlapping before merging intervals while index < total_intervals and intervals[index][1] < new_interval[0]: merged_intervals.append(intervals[index]) index += 1 # Case 2: Overlapping and merging intervals while index < total_intervals and new_interval[1] >= intervals[index][0]: new_interval[0] = min(new_interval[0], intervals[index][0]) new_interval[1] = max(new_interval[1], intervals[index][1]) index += 1 merged_intervals.append(new_interval) # Case 3: No overlapping after merging new_interval while index < total_intervals: merged_intervals.append(intervals[index]) index += 1 return merged_intervals
I think understanding the cycle update and doing it with an outer loop is something that people would more likely come up in the interview! I wonder what is the better way to solve this in actual interview
Wow amazing way to code was stuck in this for long time best way to approach this problem! Here is my java code: class Solution { public int[][] insert(int[][] intervals, int[] newInterval) { int newS=newInterval[0]; int newE=newInterval[1]; ArrayList arr=new ArrayList(); int i=0; for(i=0;i
I was thinking the same idea, then I noticed we don’t know at most how many intervals we need to merge with the newinterval, so it’s still O(n) time complexity
@@cantellmenow No, that will still lead to O(n) complexity, here's the start of the binary search solution: # O(log n) start = bisect_left(intervals, newInterval[0], key=lambda x: x[0]) # insight: since intervals are non-overlapping, that means they're sorted by end too # so find where newInterval end fits using binary search again # O(log n) end = bisect_left(intervals, newInterval[1], lo=start, key=lambda x: x[1]) # if there is more than 1 interval in between, delete intermediary ones and set edges # O(n) = 2: for _ in range(start+1, end): del intervals[start+1]
Both the start points and the end points are already sorted, so you can run two binary searches to find the merge positions. The problem is that building the output array is O(n) anyway, so it doesn't save you any time complexity.
Another way to do this problem if you've already solved merge interval, is to just add the new interval to the sorted list, sort again and then apply the same merge interval algorithm.
If you did this, you'd be tacking on O(n log n) time for sorting and O(n) space for sorting, unnecessarily. Yes, this is another way to do the problem. However, it worsens efficiency and memory.
@@JackWutang Since the given intervals were already sorted, we can simply find the inserting index using the start time, insert it and do merge interval.
I have a question in these interval question, You sometime used for loop with for i in range(len(intervals)): and sometimes with for start, end in intervals[1:]: How do we decide when to use which style would help better in any unknown problem? Thanks in advance if someone is trying to answer this
An alternate solution, O(N): def insert(intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]: # Append new interval to current list in sorted order bisect.insort_left(intervals, newInterval) updated_intervals = [] # start and end of first interval are markers, loop starts 2nd interval onwards prev_start = intervals[0][0] prev_end = intervals[0][1] for s, e in intervals[1:]: if s
curious to know what software and hardware do you use to draw and explain this problem beautifully? I can use it for my own practice while solving the problems.
When I tried it, it was a lot messy, missing multiple edge cases, this clean approach looks so good. Just wondering how much practice does it take to think of approaches like this ourself.
great video. wondering if there's a follow up with the binary search version? I feel like there are more edge cases to consider there. sidenote: although true, worst time is not improved by binary solution, it will likely speed up the process if there are many items in intervals and newInterval has a large range.
We weren't able to see the leetcode runtime of the solution at the end after you submitted because you didn't zoom out enough. If you could make sure to do that in future videos, that would be awesome. Great video though
That doesn't matter to be honest. The time complexity/space complexity are the most important parts. If you submit the same solution 3 times on leetcode you'll get 3 different leetcode runtimes. If you don't believe me, try it.
Thanks for great content! Could someone explain, I can't understand: your code should append new interval to the end all the time, even if they overlapped in the middle, so result is not sorted anymore, but when I see results - they are sorted. How?
If there's overlap in the middle, the loop will terminate in the first if clause on the next loop iteration (as long as newInterval doesn't overlap any other interval)
Aren't you supposed to return the original array 'intervals' after 'inserting' newInterval into intervals and return the original array 'intervals'? Using auxillary O(N) space makes the problem trivial to solve.
@@brianboylen9111 yes indeed. Best case, Big Omega is log n, Big O remains n with the scenario you described but I suppose it’s worth being aware of the log n early termination condition.
I thought the same thing when I first read the problem because of keywords, "sorted array" "insert at"...I personally would do a binary search for the starting interval position, then another binary search for ending interval position. logn + logn = logn
@@dorondavid4698 Yeah that's legit but it's a bit of fussy solution to code up in like 15 minutes with edge cases. At least that's the conclusion I came to.
Note that requirements of this problem has changed, and this answer is no longer correct. In the new question, you have to update the intervals array IN PLACE and you cannot create a new array to return it.
Write a helper function that checks if they DON'T overlap. This is easier since there are 4 cases of overlap versus 2 of non overlap. Non overlap: 1. A and B: a.start < b.start and a.end < b.start 2,. B and A: b.start < a.start and b.end < a.start
Think of space complexity as total space with respect to input size (in our case with input size of n, you need O(n) bytes to represent n elements in the return list).
I did the problem 'merge intervals' first so I kinda cheated on this one. I inserted the new interval into intervals, sorted intervals, and then reimplemented merge intervals. Beat 98% funnily enough. intervals.append(newInterval) intervals.sort() -- Reimplement merge intervals exactly -- done
This one kills me, I always get soooo close yet end up with a variety of edge cases. Thanks for your video.
exactly same for me, this question has my most failed submission so far
@@Oliver-Zen crazy edge cases if not thought through.
I come to your solutions first for new Leetcode problems. Sometimes I think, "wow there's got to be a more elegant way to do this." Then I look at the 🐍 solutions on Leetcode discussions and I realize how yours blows everything else out of the water.
The best part of following along with your solutions is I find myself thinking through algorithms similar to you. It's like being in the lectures of a great math professor and assimilating their thought processes into my repertoire.
seriously... a lot of the LC discussion Python solutions are these dumb one-liners that miss the point about writing readable code in interviews
Neetcode is top notch
@@roywastaken I've been working with some people that do more declarative programming via the `itertools` module (e.g. `zip`, `map`, `filter`, unpack operator `*`).
I _do_ totally agree that the one-liners are impossible to read for anyone beside the author.
_BUT_ , after I sat down and took the time to understand iterables, their iterators, and the basic `itertools`, implementing some idioms in single lines can compress the mental overhead of some leetcode solutions as I study them- even if I would expand them back out in an interview setting for legibility.
At the start of my interviews, Im definitely going to use the line "Lets right some neetcode today"
write*
HAHAHAH
wright*
whrighte*
*fight
pretty smart solution, i feel like its difficult to come up with in an interview, heres the commented code if it helps anyone:
class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
res = []
for i in range(len(intervals)):
if newInterval[1] < intervals[i][0]: # Right bound of of new interval is to the left of current interval
res.append(newInterval)
return res + intervals[i:]
elif newInterval[0] > intervals[i][1]: # Left bound of new interval is to the right of current interval
res.append(intervals[i])
else: # Some part of the the new interval is overlapping with the current interval
newInterval = [min(newInterval[0], intervals[i][0]), max(newInterval[1], intervals[i][1])]
res.append(newInterval)
return res
Your solution is so compact and clean, mine had 2 separate while loops, then a for loop to get the answer, this is way cleaner and better. This also opened my mind to how to think about this problem more logically.
Thank you! Liked!
You could do this and avoid returning twice
res = []
i, n = 0, len(intervals)
while i < n:
if newInterval[1] < intervals[i][0]:
break
elif newInterval[0] > intervals[i][1]:
res.append(intervals[i])
else:
newInterval = [min(newInterval[0],intervals[i][0]),max(newInterval[1],intervals[i][1])]
i+=1
res.append(newInterval)
return res + intervals[i:]
Deceptively tricky. Lots of edge cases to consider.
yepp
now it is a must after solving problems, watching your explanation. this is absoultely amazing. i didn't think of expanding the new interval array so i had to make a lot of cases and plus, conditions you wrote look amazingly easy. knowing well what exactly you have to do. thanks a lot. i learned a lot today too
Just can't emphasize enough how good you explain a problem!
Dude you upload faster than I can solve each day
Clever solution using the for loop to basically ignore all the intervals that are in between newInterval.
I did line sweep algorithm that was rather messy, but this way was much more elegant and efficient. An especially great solution for this one!
Stack Solution
Different Perspective
class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
# Time: O(n)
# Space: O(n)
res = [newInterval]
for n in intervals:
start, end = n
iStart, iEnd = res.pop()
# Compressing from Left Side
if start = iStart :
res.append([start, max(iEnd, end)])
# Compressing from Right Side
elif iStart = start :
res.append([iStart, max(iEnd, end)])
#Inserting in Ascending Order with No Compression
elif start < iStart:
res.append([start, end])
res.append([iStart, iEnd])
else:
res.append([iStart, iEnd])
res.append([start, end])
return res
Shouldn't our insert routine modify the original intervals array in place?
This code is compact but a bit hard to understand. If the multi-return can be reduced to a single return, then it will look more intuitive
from typing import List
class Solution:
def insert(
self, intervals: List[List[int]], newInterval: List[int]
) -> List[List[int]]:
res = []
added = False
for i in range(len(intervals)):
if newInterval[1] < intervals[i][0]:
res.append(newInterval)
res += intervals[i:]
added = True
break
elif newInterval[0] > intervals[i][1]:
res.append(intervals[i])
else:
newInterval = [
min(newInterval[0], intervals[i][0]),
max(newInterval[1], intervals[i][1]),
]
if not added:
res.append(newInterval)
return res
one of the most clearest explaination
A more interesting question would be how to store these intervals such that insertion will take less than O(N), that we don't need to iterate.
Preparing with your videos is really fun! Thanks!
Pure gold! Saved lots of time finding solution. Great explanation.
Cleaner Solution from LC:
class Solution:
def insert(
self, intervals: List[List[int]], new_interval: List[int]
) -> List[List[int]]:
total_intervals = len(intervals)
index = 0
merged_intervals = []
# Case 1: No overlapping before merging intervals
while index < total_intervals and intervals[index][1] < new_interval[0]:
merged_intervals.append(intervals[index])
index += 1
# Case 2: Overlapping and merging intervals
while index < total_intervals and new_interval[1] >= intervals[index][0]:
new_interval[0] = min(new_interval[0], intervals[index][0])
new_interval[1] = max(new_interval[1], intervals[index][1])
index += 1
merged_intervals.append(new_interval)
# Case 3: No overlapping after merging new_interval
while index < total_intervals:
merged_intervals.append(intervals[index])
index += 1
return merged_intervals
Your explanation is very easy to understand and helpful. Thank you for such a nice video.
No doubt you are at Google. Really clean and simple code
ascending order = [ [ 1, 2 ] , [ 3 , 4 ] ]
non- decreasing order = [ [ 1, 2 ] , [2, 3] ]
I think understanding the cycle update and doing it with an outer loop is something that people would more likely come up in the interview! I wonder what is the better way to solve this in actual interview
This is need to be done in-place, since they have asked us to return 'interval'.
You explained the logic and code very easily. I code in C++ but easily understood python solution
the C++ solution for this one is a nightmare imo
@@muhammadtaimoor876 just a bit of coding practice
Wow amazing way to code was stuck in this for long time best way to approach this problem!
Here is my java code:
class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
int newS=newInterval[0];
int newE=newInterval[1];
ArrayList arr=new ArrayList();
int i=0;
for(i=0;i
Thoughts on using binary search to find the insertion point? considering that theyre sorted, would improve on time complexity
I was thinking the same idea, then I noticed we don’t know at most how many intervals we need to merge with the newinterval, so it’s still O(n) time complexity
Thanks for this explanation!
@@Nora-pc6gy Do a second binary search.
@@cantellmenow No, that will still lead to O(n) complexity, here's the start of the binary search solution:
# O(log n)
start = bisect_left(intervals, newInterval[0], key=lambda x: x[0])
# insight: since intervals are non-overlapping, that means they're sorted by end too
# so find where newInterval end fits using binary search again
# O(log n)
end = bisect_left(intervals, newInterval[1], lo=start, key=lambda x: x[1])
# if there is more than 1 interval in between, delete intermediary ones and set edges
# O(n) = 2:
for _ in range(start+1, end):
del intervals[start+1]
Both the start points and the end points are already sorted, so you can run two binary searches to find the merge positions. The problem is that building the output array is O(n) anyway, so it doesn't save you any time complexity.
This one was so intuitive.
Another way to do this problem if you've already solved merge interval, is to just add the new interval to the sorted list, sort again and then apply the same merge interval algorithm.
If you did this, you'd be tacking on O(n log n) time for sorting and O(n) space for sorting, unnecessarily. Yes, this is another way to do the problem. However, it worsens efficiency and memory.
@@JackWutang Since the given intervals were already sorted, we can simply find the inserting index using the start time, insert it and do merge interval.
Java code:
public int[][] insert(int[][] intervals, int[] newInterval) {
int n = intervals.length;
LinkedList l = new LinkedList();
for(int i=0; i
I have a question in these interval question,
You sometime used for loop with
for i in range(len(intervals)):
and sometimes with
for start, end in intervals[1:]:
How do we decide when to use which style would help better in any unknown problem?
Thanks in advance if someone is trying to answer this
An alternate solution, O(N):
def insert(intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
# Append new interval to current list in sorted order
bisect.insort_left(intervals, newInterval)
updated_intervals = []
# start and end of first interval are markers, loop starts 2nd interval onwards
prev_start = intervals[0][0]
prev_end = intervals[0][1]
for s, e in intervals[1:]:
if s
curious to know what software and hardware do you use to draw and explain this problem beautifully? I can use it for my own practice while solving the problems.
he uses Paint 3D (comes with Windows). also OneNote Microsoft is good
Such an elegant code!
such elegant solution, thank you!
I think the good habit would be writing small comments throughout the code to memo the logic in more easy to decifer when u have any issue
You can solve this problem just using the idea of merge intervals, try to think about that way, it is easier and faster solution
at 5:05 you made a smiley face with the right circle/point
When I tried it, it was a lot messy, missing multiple edge cases, this clean approach looks so good. Just wondering how much practice does it take to think of approaches like this ourself.
Since the inputs are sorted, couldn't you make it O(log(n)) by identifying the positions for insertion/merge with a binary search?
yes
Yes but the insertion and merging will still be O(n).
@@MVandoff You can do another binary search using the end of inserted interval.
I think we can use binary search to reduce time complexity here
this is just merged intervals. just add the newinterval into the intervals array and run merged intervals, no need to do the extra checking
very good catch
This a great solution! Simple, elegant, and efficient.
great video. wondering if there's a follow up with the binary search version? I feel like there are more edge cases to consider there. sidenote: although true, worst time is not improved by binary solution, it will likely speed up the process if there are many items in intervals and newInterval has a large range.
We weren't able to see the leetcode runtime of the solution at the end after you submitted because you didn't zoom out enough. If you could make sure to do that in future videos, that would be awesome. Great video though
That doesn't matter to be honest. The time complexity/space complexity are the most important parts. If you submit the same solution 3 times on leetcode you'll get 3 different leetcode runtimes. If you don't believe me, try it.
Oh my, this is so elegant!
Thanks for great content! Could someone explain, I can't understand: your code should append new interval to the end all the time, even if they overlapped in the middle, so result is not sorted anymore, but when I see results - they are sorted. How?
If there's overlap in the middle, the loop will terminate in the first if clause on the next loop iteration (as long as newInterval doesn't overlap any other interval)
Thank you for this.
Hey Neet, could u make a video about ' Number of Closed Islands' ?
Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Lets write some more neetcode today
Aren't you supposed to return the original array 'intervals' after 'inserting' newInterval into intervals and return the original array 'intervals'? Using auxillary O(N) space makes the problem trivial to solve.
Doesn't it append the newInterval to the end of the res? How is that working?
Exactly what I was thinking
Very Good Explanation
U a God - This explanation is way better than the Leetcode's solution
Awesome man, Thank you 💕💕
Great solution! Pretty neat :)
Mine had lots of if-else :P
Great explanation, thanks!
Just wounding can this be solved in log(n) using binary search
Wouldn't the space complexity be O(n^2) bc the result array is a List of Lists? Or does each list here only count as one element?
Each list counts as one element since its length is constant ie. 2
This problem took me forever because I had no idea Wtf that question was asking.
you are a magician
How about O(log n) with a binary search to search where to insert the interval.
Worst case you have to add everything into one big interval which is O(n). Don't think there is any way to get O(log n)
@@brianboylen9111 yes indeed. Best case, Big Omega is log n, Big O remains n with the scenario you described but I suppose it’s worth being aware of the log n early termination condition.
I thought the same thing when I first read the problem because of keywords, "sorted array" "insert at"...I personally would do a binary search for the starting interval position, then another binary search for ending interval position. logn + logn = logn
@@dorondavid4698 Yeah that's legit but it's a bit of fussy solution to code up in like 15 minutes with edge cases. At least that's the conclusion I came to.
@@eugenevedensky6071 Its not too bad, but you can mention it to the interviewer and see what they say as well, and if they want you to code it
You're the best !!!!
Note that requirements of this problem has changed, and this answer is no longer correct. In the new question, you have to update the intervals array IN PLACE and you cannot create a new array to return it.
You are legend!!!
use exactly the same code and gives error. index out of range
Hmm wouldn't this cause the interval to be inserted twice potentially?
I am not able to understand this concept of interval !! Help me plz !! :😢
The main thing you missed here is the binary search.
Took me 3 hours to solve this :(
butter smooth
clever trick!
this problem needs a complex coding ability
Can you please solve problem no 228
how to find if overlapping or not @5:00
Write a helper function that checks if they DON'T overlap. This is easier since there are 4 cases of overlap versus 2 of non overlap.
Non overlap:
1. A and B: a.start < b.start and a.end < b.start
2,. B and A: b.start < a.start and b.end < a.start
Brother Which Book Is good or best for python data structures and algorithms for beginners
This will help you a lot.
ruclips.net/video/s91gEKf92K4/видео.html&ab_channel=AppMillers
I missed your videos :D Hope you are doing well!
HI, do you have plan to start a new channel or add videos on interview design questions
r u alive. Got placed in faang?
He did
elegant solution but was only 5% faster than the all the python submissions : /
is there a O(log(n)) time and O(1) space solution using binary search and working on the input list directly?
Good explanation!!!
so glad for the playback speed option
yeah you must have watched slowing it down lmfao
why was this medium? it feels like i've seen a number of "easy" ones harder than this
How is it medium? It is easy as for me
I take it back 😢
Plz Can you make a video on “snakes and ladders”
Why is the space complexity O(N)?! The output array space is not counted as auxiliary space right? Then we are not using any extra space.
Think of space complexity as total space with respect to input size (in our case with input size of n, you need O(n) bytes to represent n elements in the return list).
right the space complexity is O(1)
Spent a good 4 hours banging my head against this one
This is probably the hardest interval question
amongus
amongus
amongus
amongus
why?
AMOGUS
Are u alive? Y no videos mate.
Does anyone know similar questions to this on leetcode?
I did the problem 'merge intervals' first so I kinda cheated on this one. I inserted the new interval into intervals, sorted intervals, and then reimplemented merge intervals. Beat 98% funnily enough.
intervals.append(newInterval)
intervals.sort()
-- Reimplement merge intervals exactly --
done
Time complexity would be O(nlogn) because of sort()
you don't really need to sort. just check if current interval comes before the last interval in res. If so insert it before the last
java code + explanation
ruclips.net/video/g_1Hp2zJSW4/видео.htmlsi=WUxvZHbhzOKRzqzB