## 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 <= 104`
• `intervals[i].length == 2`
• `0 <= starti <= endi <= 105`
• `intervals` is sorted by ```start i``` in ascending order.
• `newInterval.length == 2`
• `0 <= 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] < newInterval:
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] <= newInterval:
newInterval = min(newInterval, intervals[i])
newInterval = max(newInterval, intervals[i])
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, interval)
upper = min(newInterval, interval)

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] < newInterval 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 = min(newInterval, intervals[i])
newInterval = max(newInterval, intervals[i])
i += 1
# Append results to output
out.append(newInterval)

while i < n:
out.append(intervals[i])
i += 1

return out
``````