Insert Interval

Medium Intervals Basics Original on LeetCode

Insert Interval is a medium intervals problem solved with the basics pattern. The best approach, optimal (one linear pass in three phases), runs in O(n) time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (append, sort, merge) up.

Problem

You have a list of intervals intervals, where intervals[i] = [start_i, end_i]. The list is sorted by start, and no two intervals in it overlap. You also get one more interval, newInterval = [start, end].

Insert newInterval so that the list is still sorted by start and still has no overlapping intervals, merging wherever needed. Intervals that share an endpoint count as overlapping. Return the resulting list.

Examples

Example 1

Input
intervals = [[1, 2], [4, 6], [9, 12]], newInterval = [5, 10]
Output
[[1, 2], [4, 12]]
Why
[5, 10] overlaps both [4, 6] and [9, 12], so the three fuse into [4, 12].

Example 2

Input
intervals = [], newInterval = [3, 3]
Output
[[3, 3]]
Why
With nothing to merge, the new interval is the whole answer.

Example 3

Input
intervals = [[2, 3], [7, 8]], newInterval = [4, 5]
Output
[[2, 3], [4, 5], [7, 8]]
Why
[4, 5] touches nothing and simply slots in between.

Constraints

  • 0 <= intervals.length <= 10^4
  • intervals[i].length == 2 and 0 <= start_i <= end_i <= 10^5
  • intervals is sorted by start and no two of its intervals overlap.
  • newInterval.length == 2 and 0 <= start <= end <= 10^5

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (append, sort, merge)O(n log n)O(n)
Optimal (one linear pass in three phases)O(n)O(n)

1Brute force (append, sort, merge)

TimeO(n log n)Sorting n + 1 intervals dominates; the merge is linear.
SpaceO(n)The combined list and the output.

Ignore the fact that the list is sorted. Add the new interval to the list, sort everything by start, then do the standard merge: walk in order and extend the last merged interval whenever the next one starts at or before its end.

  1. Copy all intervals plus newInterval into one list.
  2. Sort the list by start.
  3. For each interval: if the result is empty or the last end < this start, append it; otherwise last end = max(last end, this end).
  4. Return the result.
class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> all = new ArrayList<>();
        for (int[] iv : intervals) {
            all.add(new int[] { iv[0], iv[1] });
        }
        all.add(new int[] { newInterval[0], newInterval[1] });
        all.sort((a, b) -> Integer.compare(a[0], b[0]));
        List<int[]> res = new ArrayList<>();
        for (int[] iv : all) {
            if (res.isEmpty() || res.get(res.size() - 1)[1] < iv[0]) {
                res.add(iv);
            } else {
                int[] last = res.get(res.size() - 1);
                last[1] = Math.max(last[1], iv[1]);
            }
        }
        return res.toArray(new int[0][]);
    }
}

2Optimal (one linear pass in three phases)

TimeO(n)Each interval is visited exactly once.
SpaceO(n)Only the output list (O(1) extra beyond it).

Since the list is sorted and disjoint, walk it once. First copy every interval that ends before the new one starts. Then absorb every interval that starts at or before the new one's end, widening the new interval to cover it. Add the widened interval, then copy everything that is left.

  1. i = 0. While intervals[i].end < newStart: append intervals[i], i++.
  2. While intervals[i].start <= newEnd: newStart = min(newStart, start), newEnd = max(newEnd, end), i++.
  3. Append [newStart, newEnd].
  4. Append the remaining intervals unchanged.
class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> res = new ArrayList<>();
        int n = intervals.length, i = 0;
        int start = newInterval[0], end = newInterval[1];
        while (i < n && intervals[i][1] < start) {
            res.add(intervals[i]);
            i++;
        }
        while (i < n && intervals[i][0] <= end) {
            start = Math.min(start, intervals[i][0]);
            end = Math.max(end, intervals[i][1]);
            i++;
        }
        res.add(new int[] { start, end });
        while (i < n) {
            res.add(intervals[i]);
            i++;
        }
        return res.toArray(new int[0][]);
    }
}

Edge cases to test

  • Empty intervals
  • The new interval lies before all others or after all others
  • Intervals that only touch at an endpoint, like [1, 3] and [3, 5], count as overlapping
  • The new interval swallows every existing interval
  • The new interval sits fully inside one existing interval

Hints

Hint 1

The input is already sorted and disjoint. Which existing intervals can the new one possibly affect?

Hint 2

Split the list into three groups: those ending before the new one starts, those overlapping it, and those starting after it ends.

Hint 3

Overlapping intervals all merge into one: take the minimum start and the maximum end.

FAQ

What is the best time complexity for Insert Interval?

Optimal (one linear pass in three phases) runs in O(n) time and O(n) extra space. Each interval is visited exactly once.

Which pattern does Insert Interval use?

It is a intervals problem that uses the basics pattern. Other problems with the same pattern: Detect overlap unsorted, Detect overlap sorted intervals, Interval List Intersections.

Is there a brute force solution for Insert Interval?

Yes. Brute force (append, sort, merge) takes O(n log n) time and O(n) space. Ignore the fact that the list is sorted.

Which edge cases should I test for Insert Interval?

Empty intervals; The new interval lies before all others or after all others; Intervals that only touch at an endpoint, like [1, 3] and [3, 5], count as overlapping; The new interval swallows every existing interval; The new interval sits fully inside one existing interval.