Introduction
Sebastian (🧔🏼) and Carl (👨) been working through the Grind 75 to prepare for their upcoming interviews at MAANG. Back in university they made a great team and they believe that they can nail their coding interview prep by explaining their Leetcode solutions to each other. Sebastian meets with Carl at the hip little coffee show down on 8th street for their bi-weekly group study session.
🧔🏼 “I’ll start off with Leetcode 57, the insert interval problem. I think it’s a good introduction to interval problems.”
👨 “Alrighty Sebastian, I solved that one yesterday and I’m interested in seeing how you did it. I feel like the way I did it was a bit convoluted.”
🧔🏼 “Yeah, I saw some solutions online that were a bit harder than I think they needed to be. Anyways, let’s read the problem statement as a refresher and get started!”
👨 “Let’s do it!”
Problem Statement
You are given an array of non-overlapping intervals intervals where intervals[i] = [start
i, end
i] represent the start and the end of the ith interval and intervals is sorted in ascending order by start
i. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.
Insert newInterval into intervals such that intervals is still sorted in ascending order by start
i and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).
Return intervals after the insertion.
Examples
Example 1:
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
Example 2:
Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].
Constraints
0 <= intervals.length <= 104intervals[i].length == 20 <= starti <= endi <= 105intervalsis sorted bystart iin ascending order.newInterval.length == 20 <= start <= end <= 105
🧔🏼 “In the problem statement we are told that we have a list of non-overlapping intervals which are sorted in ascending order by the start time and we need to insert a new newInterval. When we do this, we will have to merge any overlapping intervals that may arise and the final intervals list must be sorted in the same order.”
👨 “So far so clear. Why don’t you explain it as if you were explaining it to an interviewer?”
👨 “Ok, it seems like you’re going straight to the optimized solution?”
🧔🏼 “Yeah, I have an idea that I think might work. I will separate the number line into three sections. The first section will contain the intervals whose end values are less than the start value of the newInterval. The second section will contain intervals whose start values are less than or equal to the end value of the newInterval. And finally, the third section will contain the rest of the intervals.”
👨 “This is sounding fairly straight forward. I went about it a slightly different way–probably a bit of a harder way…”
🧔🏼 Sebastian nods his head and continues, “I can loop over the intervals in the first section and add them to my out list. This loop will run as long as i < n and the end value of the ith interval is less than the start value of the newInterval. In the second section, the loop will run as long as i < n and the start value of the interval is less than or equal to the end value of the newInterval. While this loop is running, I will need to update the newInterval start and end values until the last overlapping intervals have been merged. Once the loop terminates, I can add the finalized newInterval to the out list. Lastly, I can move on to the third section and loop through the remaining intervals and add them to my out list. Here’s the code I wrote up for it.”
Python Solution 1
class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
"""
T: O(N)
S: O(1) ~ If we don't count the output array
"""
i, n = 0, len(intervals)
out = []
# Add intervals before newInterval to output list.
while i < n and intervals[i][1] < newInterval[0]:
out.append(intervals[i])
i += 1
# Merge intervals with newInterval as long as the
# start of the interval is less than or equal to
# the end of the newInterval.
while i < n and intervals[i][0] <= newInterval[1]:
newInterval[0] = min(newInterval[0], intervals[i][0])
newInterval[1] = max(newInterval[1], intervals[i][1])
i += 1
# Add merged interval to output list.
out.append(newInterval)
# Add remaining interval to output list.
while i < n:
out.append(intervals[i])
i += 1
return out
👨 “I like this solution, it’s very clear. What the time and space complexity?”
🧔🏼 “The time complexity is simply O(N) as I only need to perform one pass. The space complexity would be O(N) if I counted the output array. But a lot of times you can disregard the output when calculating space complexity. If that’s the case, our space complexity will be O(1).
Sebastian and Carl take a break and talk about girls for a while before going back and working on another problem.
Python Solution 2
The following solution uses an is_overlapping(...) function to determine overlap.
class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
i, n = 0, len(intervals)
out = []
# Determine if intervals are overlapping
# return bool
def is_overlapping(interval: List[List[int]]) -> bool:
lower = max(newInterval[0], interval[0])
upper = min(newInterval[1], interval[1])
return (upper - lower >= 0)
# Loop over intervals while:
# 1) interval_start < new_start
# 2) intervals overlap
# We don't want to sort the results once we're done, we need to ensure that we
# only add intervals that occur before the newInterval
while i < n and intervals[i][1] < newInterval[0] and not is_overlapping(intervals[i]):
out.append(intervals[i])
i += 1
# Merge overlapping intervals
# 1) set the new lower limit
# 2) set the new upper limit
while i < n and is_overlapping(intervals[i]):
newInterval[0] = min(newInterval[0], intervals[i][0])
newInterval[1] = max(newInterval[1], intervals[i][1])
i += 1
# Append results to output
out.append(newInterval)
while i < n:
out.append(intervals[i])
i += 1
return out