57. Insert Interval - Explanation

Description

You are given an array of non-overlapping intervals intervals where intervals[i] = [start_i, end_i] represents the start and the end time of the ith interval. intervals is initially sorted in ascending order by start_i.

You are given another interval newInterval = [start, end].

Insert newInterval into intervals such that intervals is still sorted in ascending order by start_i and also intervals still does not have any overlapping intervals. You may merge the overlapping intervals if needed.

Return intervals after adding newInterval.

Note: Intervals are non-overlapping if they have no common point. For example, [1,2] and [3,4] are non-overlapping, but [1,2] and [2,3] are overlapping.

Example 1:

Input: intervals = [[1,3],[4,6]], newInterval = [2,5]

Output: [[1,6]]

Example 2:

Input: intervals = [[1,2],[3,5],[9,10]], newInterval = [6,7]

Output: [[1,2],[3,5],[6,7],[9,10]]

Constraints:

0 <= intervals.length <= 1000
newInterval.length == intervals[i].length == 2
0 <= start <= end <= 1000

Recommended Time & Space Complexity

You should aim for a solution with O(n) time and O(1) extra space, where n is the size of the input array.

Hint 1

The given intervals are non-overlapping and sorted in ascending order based on the start value. Try to visualize them as line segments and consider how a new interval can be inserted. Maybe you should analyze different cases of inserting a new interval.

Hint 2

First, we append all intervals to the output list that have an end value smaller than the start value of the new interval. Then, we encounter one of three cases: we have appended all intervals, we reach an interval whose start value is greater than the new interval’s end, or we find an overlapping interval. Can you think of a way to handle these cases efficiently?

Hint 3

We iterate through the remaining intervals, updating the new interval if its end value is greater than or equal to the current interval's start value. We adjust the start and end of the new interval to the minimum and maximum values, respectively. After this, any remaining intervals are appended to the output list, and we return the result.

Company Tags

1. Linear Search

Intuition

We are given a list of non-overlapping intervals sorted by start time, and we need to insert newInterval into the list while keeping the result sorted and non-overlapping.

Since the intervals are already sorted, we can process them in one pass and split the work into three simple parts:

Intervals completely before newInterval
- These do not overlap, so we can add them directly to the result.
Intervals that overlap with newInterval
- While there is overlap, we merge them by expanding newInterval:
  - new start = minimum of starts
  - new end = maximum of ends
Intervals completely after the merged newInterval
- These also do not overlap, so we add them directly.

This way, we only scan the list once and merge exactly when needed.

Algorithm

Initialize an empty result list res and index i = 0.
Add all intervals that end before newInterval starts:
- while intervals[i].end < newInterval.start, append intervals[i] to res
Merge all intervals that overlap with newInterval:
- while intervals[i].start <= newInterval.end, update:
  - newInterval.start = min(newInterval.start, intervals[i].start)
  - newInterval.end = max(newInterval.end, intervals[i].end)
Append the merged newInterval to res.
Append all remaining intervals (which must come after) to res.
Return res.

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        n = len(intervals)
        i = 0
        res = []

        while i < n and intervals[i][1] < newInterval[0]:
            res.append(intervals[i])
            i += 1

        while i < n and newInterval[1] >= intervals[i][0]:
            newInterval[0] = min(newInterval[0], intervals[i][0])
            newInterval[1] = max(newInterval[1], intervals[i][1])
            i += 1
        res.append(newInterval)

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

        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity:
- $O(1)$ extra space.
- $O(n)$ space for the output list.

2. Binary Search

Intuition

We are given a list of non-overlapping intervals sorted by start time, and we want to insert newInterval while keeping the final list sorted and merged.

A simple idea is:

Use binary search to find the correct position where newInterval should be inserted based on its start time.
After inserting, the list is still sorted by start time.
Then we do a normal merge intervals pass:
- if the current interval does not overlap the last interval in the result, append it
- otherwise merge them by extending the end

Binary search helps us avoid scanning from the beginning just to find the insertion position.

Algorithm

If the list is empty, return [newInterval].
Use binary search to find the first index left where:
- intervals[left].start >= newInterval.start
- this is the position where newInterval should be inserted
Insert newInterval into intervals at index left.
Initialize an empty list res.
Iterate through the (now sorted) intervals:
- If res is empty or the current interval starts after the last interval in res ends:
  - append the current interval to res
- Otherwise (overlap exists):
  - merge by updating the last interval’s end:
    - res[-1].end = max(res[-1].end, current.end)
Return res.

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        if not intervals:
            return [newInterval]

        n = len(intervals)
        target = newInterval[0]
        left, right = 0, n - 1

        while left <= right:
            mid = (left + right) // 2
            if intervals[mid][0] < target:
                left = mid + 1
            else:
                right = mid - 1

        intervals.insert(left, newInterval)

        res = []
        for interval in intervals:
            if not res or res[-1][1] < interval[0]:
                res.append(interval)
            else:
                res[-1][1] = max(res[-1][1], interval[1])
        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity:
- $O(1)$ extra space.
- $O(n)$ space for the output list.

3. Greedy

Intuition

We are inserting newInterval into a list of sorted, non-overlapping intervals and want the final result to remain sorted and non-overlapping.

A greedy approach works because as we scan from left to right, every interval falls into one of three cases relative to newInterval:

Completely after newInterval
- If newInterval ends before the current interval starts, there will be no overlap with any later interval either.
- So we can safely place newInterval here and return the answer immediately.
Completely before newInterval
- If the current interval ends before newInterval starts, it can be added to the result unchanged.
Overlapping with newInterval
- If they overlap, we merge them by expanding newInterval to cover both ranges.

By continuously merging when needed and stopping early when newInterval is placed, we solve it in one pass.

Algorithm

Initialize an empty list res.
Iterate through each interval in intervals:
If newInterval ends before the current interval starts:
- Append newInterval to res
- Return res plus the remaining intervals (since everything after is already sorted and non-overlapping)
Else if newInterval starts after the current interval ends:
- Append the current interval to res (it is safely before newInterval)
Else (they overlap):
- Merge by updating newInterval:
  - newInterval.start = min(newInterval.start, interval.start)
  - newInterval.end = max(newInterval.end, interval.end)
If the loop ends, it means newInterval belongs at the end:
- Append newInterval to res
Return res

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]:
                res.append(newInterval)
                return res + intervals[i:]
            elif newInterval[0] > intervals[i][1]:
                res.append(intervals[i])
            else:
                newInterval = [
                    min(newInterval[0], intervals[i][0]),
                    max(newInterval[1], intervals[i][1]),
                ]
        res.append(newInterval)
        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity:
- $O(1)$ extra space.
- $O(n)$ space for the output list.