Insert Interval

Medium Problem 142 of 151 Java and Python

Problem

You are given a list of non-overlapping intervals sorted by start, and a newInterval. Insert newInterval so that the list stays sorted and non-overlapping, merging intervals where necessary. Return the result.

Example 1

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

Example 2

Input: intervals = [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], newInterval = [4, 8]
Output: [[1, 2], [3, 10], [12, 16]]
Why: [4, 8] overlaps [3, 5], [6, 7] and [8, 10].

Constraints

0 ≤ intervals.length ≤ 10⁴
intervals is sorted by start and non-overlapping.

Explanation

The input is already sorted, so there are three zones: intervals that end before the new one starts (copy them), intervals that overlap it (fold them into it), and intervals that start after it ends (copy them).

Approach 1 · Naive

Append, then Merge Intervals

Time O(n log n)
Space O(n)

Add the new interval to the list and run the sort-and-merge algorithm.

Append newInterval.
Sort by start and merge overlapping intervals.

Java

import java.util.*;

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> all = new ArrayList<>();
        for (int[] interval : intervals) {
            all.add(interval.clone());
        }
        all.add(newInterval.clone());
        all.sort((a, b) -> Integer.compare(a[0], b[0]));
        List<int[]> merged = new ArrayList<>();
        for (int[] interval : all) {
            if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < interval[0]) {
                merged.add(interval);
            } else {
                int[] last = merged.get(merged.size() - 1);
                last[1] = Math.max(last[1], interval[1]);
            }
        }
        return merged.toArray(new int[0][]);
    }
}

Python

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        merged = []
        for start, end in sorted(intervals + [newInterval]):
            if not merged or merged[-1][1] < start:
                merged.append([start, end])
            else:
                merged[-1][1] = max(merged[-1][1], end)
        return merged

Approach 2 · Optimal

Three zones in one pass

Time O(n)
Space O(n) for the output

Copy the intervals that end before the new one, merge the overlapping ones into it, then copy the rest.

While intervals[i].end < new.start: copy it.
While intervals[i].start <= new.end: set new = [min starts, max ends].
Add new, then copy the remaining intervals.

Java

import java.util.*;

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> result = new ArrayList<>();
        int i = 0;
        int n = intervals.length;
        int start = newInterval[0];
        int end = newInterval[1];
        while (i < n && intervals[i][1] < start) {
            result.add(intervals[i++]);
        }
        while (i < n && 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 });
        while (i < n) {
            result.add(intervals[i++]);
        }
        return result.toArray(new int[0][]);
    }
}

Python

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        result, i, n = [], 0, len(intervals)
        start, end = newInterval
        while i < n and intervals[i][1] < start:
            result.append(intervals[i])
            i += 1
        while i < n and intervals[i][0] <= end:
            start = min(start, intervals[i][0])
            end = max(end, intervals[i][1])
            i += 1
        result.append([start, end])
        result.extend(intervals[i:])
        return result

Complexity compared

Approach	Time	Space
Naive Append, then Merge Intervals	O(n log n)	O(n)
Optimal Three zones in one pass	O(n)	O(n) for the output

Key takeaways

Use the input being sorted: it turns an O(n log n) merge into an O(n) pass.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem