Insert Interval

Q: What is the time complexity of Insert Interval?

The one pass solution runs in O(n) time, since each interval is copied or folded in once, and uses O(n) space for a result of up to n+1 intervals. Adding the interval and re-sorting takes O(n log n) .

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 sorts first. Here the list is sorted and the old intervals never touch, so only the new interval can trigger a merge, and the intervals it merges with form one run. A single pass is enough.

Q: How do you check whether two intervals overlap?

[a, b] and [c, d] share a point exactly when a ≤ d and c ≤ b . That counts touching intervals such as [2, 4] and [4, 8] as overlapping, as this problem wants. To keep touching intervals apart, use a < d and c < b .

MediumIntervals

+10

You get intervals sorted by start as two arrays: interval i is [starts[i], ends[i]], and no two overlap or touch. Insert the new interval [newStart, newEnd], merge it with every interval it overlaps or touches, and return all intervals as [start, end] pairs sorted by start.

Intervals touch when one ends where the other starts, as [2, 4] and [4, 8] do, and touching intervals merge. [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.

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, 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.

Follow-up

If you insert many intervals one after another, how would you store them so each insert costs O(log n) plus one step per 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 are sorted and apart, so only the new interval can cause a merge. That splits the list into three runs: intervals that end before it starts, intervals that overlap or touch it, and intervals that start after it ends. Copy the first run, fold the middle run into one interval, copy the last. One pass, no sorting.

Add it and merge everything again

Intuition

Reuse Merge Intervals: add the new interval, sort all n+1 intervals by start, and walk them holding the last merged interval. After the sort an interval can only overlap the group right before it, so when the next start is at or before the held end, stretch the end; otherwise a gap opens and a new interval begins.

The sort costs O(n log n) to fix a list that is out of order in one place, and it ignores that the old intervals never merge with each other.

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

The list is sorted and its intervals are apart, so the intervals that meet the new one form one unbroken run. Everything before the run has ends[i] < newStart: it finishes before the new interval begins. The test is strict because an interval that ends exactly at newStart touches the new one and must merge.

Inside the run, an interval with starts[i] ≤ mergedEnd overlaps or touches the interval you are building, so it widens it to the smaller start and the larger end. The first interval that starts after mergedEnd ends the run, since every later one starts further right. When the run is empty, the new interval goes in on its own. In the first example, [1, 3] is copied, [5, 7] and [10, 12] widen [6, 11] to [5, 12], and [15, 18] is copied. Each interval is looked at once: O(n) time, and no memory beyond the result.

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

Wrong inequalities 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. The first test is strict, the second is not.
Comparing with mergedEnd + 1. That joins [1, 2] and [3, 4], which share no point.
Keeping newStart as the merged start. [6, 11] begins inside [5, 7], so the result starts at 5.
Adding the new interval only when it overlaps something. When it lands in a gap or past either end, as [5, 6] does, the middle loop never runs, and it must still be added.
Reading starts[i] before checking i < n. A new interval that reaches past the last one runs the index off the end.

Frequently asked questions3

What is the time complexity of Insert Interval?

The one pass solution runs in O(n) time, since each interval is copied or folded in once, and uses O(n) space for a result of up to n+1 intervals. Adding the interval and re-sorting takes O(n log n).

How is Insert Interval different from Merge Intervals?

Merge Intervals starts from an unsorted list where any interval can overlap any other, so it sorts first. Here the list is sorted and the old intervals never touch, so only the new interval can trigger a merge, and the intervals it merges with form one run. A single pass is enough.

How do you check whether two intervals overlap?

[a, b] and [c, d] share a point exactly when a ≤ d and c ≤ b. That counts touching intervals such as [2, 4] and [4, 8] as overlapping, as this problem wants. To keep touching intervals apart, use a < d and c < b.

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

Test #1

Test #2

Test #3

Arguments

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

Expected Output

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