Insert Interval

Q: What is the time complexity of Insert Interval?

The one pass solution runs in O(n) time: each interval is copied or folded in exactly once. The result holds up to n+1 intervals, so it takes O(n) space, and nothing else grows with the input. Adding the interval and re-sorting takes O(n log n) instead.

Q: How is Insert Interval different from Merge Intervals?

Merge Intervals starts from an unsorted list where any interval can overlap any other, so it has to sort first. In Insert Interval the list is already sorted and the old intervals never touch each other, so only the new interval can trigger a merge. The intervals it merges with form one unbroken run, which is why a single pass without sorting is enough.

Q: How do you check whether two intervals overlap?

Intervals [a, b] and [c, d] share at least one point exactly when a ≤ d and c ≤ b . That counts touching intervals such as [2, 4] and [4, 8] as overlapping, which is what this problem wants. If touching intervals had to stay apart, you would use a < d and c < b instead.

Q: Can binary search make Insert Interval faster?

Binary search finds where the merged run begins and ends in O(log n) , because the starts and the ends are both sorted. The function still returns a new list, though, and copying the untouched intervals into it costs O(n) . So the total stays O(n) . Binary search pays off when the intervals live in a structure that can remove and insert a range without copying, such as a balanced tree.

MediumIntervals

+10

You get a list of intervals sorted by start, given as two arrays of the same length: interval i is [starts[i], ends[i]]. No two of them overlap or touch. You also get one new interval, [newStart, newEnd]. Insert it, merge it with every interval it overlaps or touches, and return all the intervals as a 2D array of [start, end] pairs, sorted by start.

Two intervals touch when one ends where the other starts, as [2, 4] and [4, 8] do, and touching intervals merge into one. [1, 2] and [3, 4] share no point, so they stay apart.

Function

insertInterval(starts: integer-array, ends: integer-array, newStart: integer, newEnd: integer) → integer-2d-array

startsinteger-array: the start of each interval, in increasing order
endsinteger-array: the end of each interval, matching starts
newStartinteger: the start of the interval to insert
newEndinteger: the end of the interval to insert
Returnsinteger-2d-array: the intervals after the insert as [start, end] pairs, sorted by start

Constraints

1 ≤ starts.length == ends.length ≤ 2000
0 ≤ starts[i] ≤ ends[i] ≤ 10⁵
ends[i] < starts[i+1]: the intervals are sorted by start, and no two of them overlap or touch.
0 ≤ newStart ≤ newEnd ≤ 10⁵

Examples

Input: starts = [1, 5, 10, 15]ends = [3, 7, 12, 18]newStart = 6newEnd = 11
Output: [[1, 3], [5, 12], [15, 18]]
Explanation: [6, 11] overlaps [5, 7] and [10, 12], so the three become [5, 12]. [1, 3] ends before 6 and [15, 18] starts after 12, so both stay as they are.

Input: starts = [2, 8]ends = [4, 9]newStart = 4newEnd = 8
Output: [[2, 9]]
Explanation: [4, 8] touches [2, 4] at 4 and [8, 9] at 8. Touching counts as overlapping, so all three join into [2, 9].

Input: starts = [1, 9]ends = [2, 10]newStart = 5newEnd = 6
Output: [[1, 2], [5, 6], [9, 10]]
Explanation: [5, 6] sits in the gap between 2 and 9 and touches neither neighbour, so it slots in between them and nothing merges.

+20 hidden tests on Submit

Follow-up

Suppose you insert many new intervals, one after another, into the same list. How would you store the intervals so that each insert costs O(log n) plus one step for every old interval it swallows?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

The old intervals already sit apart and in order, so only the new interval can cause a merge. That splits the list into three runs: intervals that end before the new one starts, intervals that overlap or touch it, and intervals that start after it ends. Copy the first run, fold the middle run into a single interval, copy the last run. One pass, no sorting.

Add it and merge everything again

Intuition

If you have solved Merge Intervals, you can reuse it here. Put the new interval into the list, sort all n+1 intervals by start, and merge. After the sort, an interval can only overlap the group right before it, so you walk the list holding the last merged interval. When the next start is at or before its end, stretch the end. Otherwise there is a real gap, and a new interval begins.

Run it on the first example. The list becomes [1, 3], [5, 7], [6, 11], [10, 12], [15, 18]. [1, 3] stands alone, since 5 is past 3. 6 is at most 7, so [5, 7] stretches to [5, 11]. 10 is at most 11, so it stretches to [5, 12]. 15 is past 12, so [15, 18] starts a new interval.

This is correct, and at 2000 intervals it runs fast. It throws away two facts you were given, though: the list is already sorted, and the old intervals never merge with each other. Paying O(n log n) to re-sort a list that is out of order in one place is the step an interviewer will ask you to remove.

Algorithm

Pair every start with its end, and add [newStart, newEnd] to the list.
Sort the intervals by start.
Walk them in order, holding the last merged interval.
If the next start is at most the held end, raise the held end to the larger of the two ends.
Otherwise append the next interval as a new merged one. Return the merged list.

def insertInterval(starts, ends, newStart, newEnd):
    intervals = list(zip(starts, ends))
    intervals.append((newStart, newEnd))
    intervals.sort()
    merged = []
    for start, end in intervals:
        if merged and start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)  # overlaps or touches: stretch
        else:
            merged.append([start, end])  # a real gap: a new interval begins
    return merged

One pass in three parts

Intuition

Walk the list once with an index i and split it into three runs. First, every interval with ends[i] < newStart finishes before the new one begins, so it shares no point with it: copy it to the result. The test is a strict < because an interval that ends exactly at newStart touches the new one and has to merge.

Second, every interval with starts[i] ≤ mergedEnd overlaps or touches the interval you are building. Fold it in: mergedStart becomes the smaller start and mergedEnd the larger end. The intervals in this run sit next to each other, because the list is sorted. Once an interval starts after mergedEnd, every later one starts even further right, so nothing past it can merge. Append the merged interval; this step also covers the case where the run is empty and the new interval goes in on its own.

Third, copy everything that is left. Those intervals start after the merged interval ends, and they were already apart from each other.

Trace the first example. [1, 3] ends before 6: copy it. [5, 7] starts at 5, which is at most 11: the merged interval becomes [5, 11]. [10, 12] starts at 10, at most 11: it becomes [5, 12]. [15, 18] starts past 12, so append [5, 12] and copy [15, 18]. Each interval is looked at once, so the time is O(n), and the only extra memory is the result itself.

Algorithm

Copy intervals to the result while ends[i] < newStart.
Set mergedStart = newStart and mergedEnd = newEnd.
While starts[i] ≤ mergedEnd, set mergedStart to the smaller start and mergedEnd to the larger end, and move on.
Append [mergedStart, mergedEnd].
Copy the remaining intervals and return the result.

def insertInterval(starts, ends, newStart, newEnd):
    n = len(starts)
    result = []
    i = 0
    # 1. Intervals that end before the new one starts stay as they are.
    while i < n and ends[i] < newStart:
        result.append([starts[i], ends[i]])
        i += 1
    # 2. Intervals that overlap or touch the new one fold into it.
    mergedStart, mergedEnd = newStart, newEnd
    while i < n and starts[i] <= mergedEnd:
        mergedStart = min(mergedStart, starts[i])
        mergedEnd = max(mergedEnd, ends[i])
        i += 1
    result.append([mergedStart, mergedEnd])
    # 3. Intervals that start after the merged one ends stay as they are.
    while i < n:
        result.append([starts[i], ends[i]])
        i += 1
    return result

Pitfalls and edge cases

The loop is short, so most bugs come from one wrong comparison or a forgotten case at the ends of the list.

Using the wrong inequality for touching intervals. With ends[i] ≤ newStart in the first loop, or starts[i] < mergedEnd in the second, [2, 4] and [4, 8] stay apart. Touching intervals merge, so the first test is strict and the second is not.
Merging intervals that only look adjacent. [1, 2] and [3, 4] share no point, so comparing with mergedEnd + 1 joins intervals that should stay separate.
Keeping newStart as the merged start. When the new interval begins inside an old one, as [6, 11] does inside [5, 7], the result starts at 5. Take the smaller of the two starts.
Appending the new interval only when it overlaps something. When it lands before every interval, after every interval, or in a gap, the middle loop never runs, and the new interval must still be added.
Reading starts[i] or ends[i] before checking i < n. When the new interval reaches past the last interval, the index runs off the end of the arrays.

Frequently asked questions4

What is the time complexity of Insert Interval?

The one pass solution runs in O(n) time: each interval is copied or folded in exactly once. The result holds up to n+1 intervals, so it takes O(n) space, and nothing else grows with the input. Adding the interval and re-sorting takes O(n log n) instead.

How is Insert Interval different from Merge Intervals?

Merge Intervals starts from an unsorted list where any interval can overlap any other, so it has to sort first. In Insert Interval the list is already sorted and the old intervals never touch each other, so only the new interval can trigger a merge. The intervals it merges with form one unbroken run, which is why a single pass without sorting is enough.

How do you check whether two intervals overlap?

Intervals [a, b] and [c, d] share at least one point exactly when a ≤ d and c ≤ b. That counts touching intervals such as [2, 4] and [4, 8] as overlapping, which is what this problem wants. If touching intervals had to stay apart, you would use a < d and c < b instead.

Can binary search make Insert Interval faster?

Binary search finds where the merged run begins and ends in O(log n), because the starts and the ends are both sorted. The function still returns a new list, though, and copying the untouched intervals into it costs O(n). So the total stays O(n). Binary search pays off when the intervals live in a structure that can remove and insert a range without copying, such as a balanced tree.

Python

def insertInterval(starts, ends, newStart, newEnd):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

starts = [1, 5, 10, 15]
ends = [3, 7, 12, 18]
newStart = 6
newEnd = 11

Expected

[[1, 3], [5, 12], [15, 18]]