Insert Interval

The problem

You are given a list intervals of n intervals [start, end] (n is the length of intervals). They do not overlap, and they are sorted by start. You are also given one more interval, new_interval.

Insert new_interval into the list. If it overlaps any intervals, merge them into one. Return the new list, still sorted and with no overlaps. Two intervals overlap if they share at least one point, so [1, 3] and [3, 5] overlap.

Example 1

Input: intervals = [[1, 2], [4, 6], [7, 8], [10, 13], [15, 17]], new_interval = [5, 11]

Output: [[1, 2], [4, 13], [15, 17]]

[5, 11] touches [4, 6], [7, 8] and [10, 13]. All four become one interval, [4, 13].

result

Example 2

Input: intervals = [], new_interval = [3, 5]

Output: [[3, 5]]

The list was empty, so the new interval is the whole answer.

Example 3

Input: intervals = [[2, 4], [8, 9]], new_interval = [5, 6]

Output: [[2, 4], [5, 6], [8, 9]]

It overlaps nothing, so it just slides into its place.

Constraints

• 0 ≤ n ≤ 10,000
• 0 ≤ start ≤ end ≤ 100,000, for every interval and for new_interval
• intervals is sorted by start and has no overlaps.

Clarifying questions

Do touching intervals overlap?

Yes. [1, 3] and [3, 5] share the point 3, so they merge into [1, 5].

Is the input sorted?

Yes, by start, and with no overlaps. That is what makes one pass enough.

Can the list be empty?

Yes. Then the answer is just the new interval.

May we change the input list?

Building a new list is cleaner, and it does not change the Big O.

Spot the pattern

Intervals sorted by start, and a question about overlaps: that is the intervals pattern. Since the list is already sorted and has no overlaps, the intervals that touch new_interval sit next to each other. So the list splits into three runs: before it, overlapping it, and after it.

Solutions

Sort and mergeO(n log n)One passO(n)

Show all

Finding the first overlap with binary search does not help: building the output list still takes O(n).

Sort and merge O(n log n)

The idea

Add the new interval to the list and sort everything by start. Now it is the Merge Intervals problem: walk the sorted list, and either stretch the last result or start a new one.

It is correct and reuses a known solution. But the input was already sorted, and the sort redoes that work.

Walkthrough

intervals

result

empty

1. everything = sorted(intervals + [new_interval])
2. result = []
3. for start, end in everything:
4. if result and start <= result[-1][1]:
5. result[-1][1] = max(result[-1][1], end)
6. else:
7. result.append([start, end])
8. return result

Add the new interval to the list, then sort everything by start. After that it is a plain merge.

← BackStep →Play1 / 9

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Sort and merge: add the new interval, sort by start, then merge in one pass.
    // The sort costs O(n log n), and the copy costs O(n) memory.
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int[][] everything = java.util.Arrays.copyOf(intervals, intervals.length + 1);
        everything[intervals.length] = newInterval;
        java.util.Arrays.sort(everything, (first, second) -> Integer.compare(first[0], second[0]));
        java.util.List<int[]> result = new java.util.ArrayList<>();
        for (int[] interval : everything) {
            // Sorted by start, so only the last result can overlap this one.
            if (!result.isEmpty() && interval[0] <= result.get(result.size() - 1)[1]) {
                int[] last = result.get(result.size() - 1);
                last[1] = Math.max(last[1], interval[1]);
            } else {
                result.add(new int[] { interval[0], interval[1] });
            }
        }
        return result.toArray(new int[0][]);
    }
}

Big O

Time O(n log n)Space O(n)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   Two parts repeat. The sort compares intervals many times. Then the loop does one comparison and one append or stretch per interval, which is 1 step per run.

   1. everything = sorted(intervals + [new_interval])
   2. result = []
   3. for start, end in everything:
   4. if result and start <= result[-1][1]:
   5. result[-1][1] = max(result[-1][1], end)
   6. else:
   7. result.append([start, end])
   8. return result

2. 2 Count the runs on Example 1

   Example 1 has 5 intervals plus the new one, so 6. Sorting 6 items takes about 6 × log₂ 6, so about 16 steps. The merge loop then runs 6 times.

   16 + 6 = about 22 steps.

   part	sort	merge loop
   steps	about 6 × log 6 ≈ 16	6

3. 3 Write the count for any n

   With n intervals, the sort handles n + 1 items and the loop runs n + 1 times:

   (n + 1) log₂(n + 1) + (n + 1)

   Check it with Example 1: 6 × 2.6 + 6 ≈ 22.

4. 4 Keep only the part that grows fastest

   Keep the sort. The sort is the biggest part: log n keeps growing, so n log n pulls away from the loop’s n. Drop the + 1s too. What is left is n log n.

   So the time is O(n log n).

5. S Space: count the extra memory the same way

   The combined list holds n + 1 intervals, and so can the result. The space is O(n).

   everything (n + 1 intervals)result (up to n + 1)

One pass O(n)

The idea

Walk the list once with an index i, in three parts.

1. Before. While an interval ends before new_interval starts, it cannot touch it. Copy it.
2. Overlap. While an interval starts before new_interval ends, they overlap. Swallow it: stretch new_interval to cover both. Then add the grown new_interval.
3. After. Every interval left starts after new_interval ends. Copy them.

Why it is correct: the input is sorted with no overlaps. So once an interval starts after new_interval ends, every later one does too. The overlapping intervals form one run in the middle.

Walkthrough

intervals

result

empty

1. result, i = [], 0
2. while i < len(intervals) and intervals[i][1] < new_interval[0]:
3. result.append(intervals[i]); i += 1
4. while i < len(intervals) and intervals[i][0] <= new_interval[1]:
5. new_interval = [min(new_interval[0], intervals[i][0]), max(new_interval[1], intervals[i][1])]; i += 1
6. result.append(new_interval)
7. while i < len(intervals):
8. result.append(intervals[i]); i += 1
9. return result

The list is already sorted. Walk it once, in three parts: before the new interval, overlapping it, and after it.

← BackStep →Play1 / 8

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // One pass: copy the intervals before the new one, swallow the ones that
    // overlap it, then copy the rest. O(n) time, O(n) for the output.
    public int[][] insert(int[][] intervals, int[] newInterval) {
        java.util.List<int[]> result = new java.util.ArrayList<>();
        int i = 0, intervalsLength = intervals.length;
        int start = newInterval[0], end = newInterval[1];
        // Ends before the new one starts: it cannot touch it.
        while (i < intervalsLength && intervals[i][1] < start) result.add(intervals[i++]);
        // Starts before the new one ends (<=, touching counts): merge it in.
        while (i < intervalsLength && intervals[i][0] <= end) {
            start = Math.min(start, intervals[i][0]);
            end = Math.max(end, intervals[i][1]);
            i++;
        }
        result.add(new int[] { start, end });
        // The list is sorted, so everything left starts after end.
        while (i < intervalsLength) result.add(intervals[i++]);
        return result.toArray(new int[0][]);
    }
}

Big O

Time O(n)Space O(n)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   There are three loops, one after the other. Each run looks at one interval and copies or swallows it. That is 1 step. All three loops move the same index i.

   1. result, i = [], 0
   2. while i < len(intervals) and intervals[i][1] < new_interval[0]:
   3. result.append(intervals[i]); i += 1
   4. while i < len(intervals) and intervals[i][0] <= new_interval[1]:
   5. new_interval = [min(new_interval[0], intervals[i][0]), max(new_interval[1], intervals[i][1])]; i += 1
   6. result.append(new_interval)
   7. while i < len(intervals):
   8. result.append(intervals[i]); i += 1
   9. return result

2. 2 Count the runs on Example 1

   Example 1 has 5 intervals. One is before, three overlap, and one is after. Then one append adds the grown interval.

   1 + 3 + 1 = 5 runs, plus 1 append.

   interval	[1, 2]	[4, 6]	[7, 8]	[10, 13]	[15, 17]
   part	before	overlap	overlap	overlap	after

   total

   5 runs + 1 append

3. 3 Write the count for any n

   The three loops share i, and i goes from 0 to n once in total:

   n runs + 1 append

   Check it with Example 1: 5 + 1 = 6.

4. 4 Keep only the part that grows fastest

   Drop the + 1. What is left is n. Three loops in a row are still one pass.

   So the time is O(n).

5. S Space: count the extra memory the same way

   The result holds up to n + 1 intervals, so the space is O(n). Beyond the output, the code only keeps i and new_interval.

   result (up to n + 1)inew_interval

Common mistake

Using < where touching counts

The overlap test must be intervals[i][0] <= new_interval[1]. With <, an interval that starts exactly where the new one ends, like [11, 12] after [5, 11], is not merged.

Tested at the limits

2,000 random lists of 0 to 5 sorted intervals with small gaps, and a new interval that often touches an end, sits in a gap, covers several intervals, or comes before or after all of them. Sort and merge and one pass gave the same answer every time.

Largest inputs	Result
10,000 intervals (the most allowed), with the new interval covering the middle half. One pass.	Under 0.001 s, and about 0.06 MB of extra memory: the result list of 5,000 intervals.
The same 10,000 intervals. Sort and merge.	0.001 s, and about 0.5 MB: it copies every interval before sorting.