Command Palette

Search for a command to run...

Hectal
Problem 15.2 · IntervalsMedium

Insert Interval

PatternMerge Intervals

What it teaches: When the list is already sorted and disjoint, one linear pass does it: copy before, merge the overlap, copy after.

Practise it on judges as “Insert Interval”.

The problem

intervals is sorted by start and non-overlapping. Insert newInterval, merging where needed, and 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]]

Constraints

  • 0 ≤ n ≤ 10⁴
  • Sorted, disjoint

Pattern clues in the wording

  • → Sorted disjoint intervals plus one new one
  • → O(n) is possible without re-sorting

These clues point to Merge Intervals: Sort intervals by start; each one either overlaps the last merged interval (extend it) or starts a new one.

Stuck? Take one hint at a time

Solution.java · starter
import java.util.*;

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        return intervals;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
intervals = [[1,3],[6,9]]
newInterval = [2,5]
[[1,5],[6,9]]
2
intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]]
newInterval = [4,8]
[[1,2],[3,10],[12,16]]
3
intervals = []
newInterval = [5,7]
[[5,7]]

From slow to fast

Approaches

1. Optimal: three phases · O(n)
1

Optimal: three phases

Time O(n) Space O(n)

Copy intervals with end < new.start. Merge every interval with start ≤ new.end into the new one (min start, max end), then add it. Copy the rest.

Approach 1
import java.util.*;

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

Verdict: One pass.

Before you submit

Edge cases and common mistakes

Test these inputs

  • Empty list
  • New interval before all or after all
  • New interval covering everything

Mistakes people make

  • Appending and re-sorting (O(n log n), fine but unnecessary).
  • Off-by-one in the overlap conditions.

Interview

Follow-up questions

How would you remove an interval range instead?