LeetCode 57 · Medium · Intervals

Insert Interval

You get a list of non-overlapping intervals sorted by start and one new interval. Insert the new one so the list stays sorted and non-overlapping, merging wherever it overlaps.

O(n)time · one pass
O(n)space · result
3 casesbefore · after · overlap

intervals: 0–8, sorted, not overlapping · newInterval: one · 0 ≤ start ≤ end ≤ 20

Number line top: intervals · middle: newInterval as it grows · bottom: res

public int[][] insert(int[][] intervals, int[] newInterval) { List<int[]> res = new ArrayList<>(); for (int i = 0; i < intervals.length; i++) { if (newInterval[1] < intervals[i][0]) { // ends before res.add(newInterval); for (int j = i; j < intervals.length; j++) { res.add(intervals[j]); } return res.toArray(new int[0][]); } else if (newInterval[0] > intervals[i][1]) { // starts after res.add(intervals[i]); } else { // overlap: grow newInterval newInterval = new int[]{ Math.min(newInterval[0], intervals[i][0]), Math.max(newInterval[1], intervals[i][1])}; } } res.add(newInterval); return res.toArray(new int[0][]);}
i
—
intervals[i]
—
newInterval
—
res
[]

Why it works

  1. Brute force appends and re-merges: add newInterval to the list, sort, and run Merge Intervals. Correct, but O(n log n) when the input is already sorted.
  2. Each interval falls in one of three cases against newInterval: it ends before (copy it to res), it starts after (place newInterval and copy the rest), or it overlaps (absorb it). Invariant: res is sorted, final, and ends before newInterval starts.
  3. Linear time: each interval is compared once and copied at most once, so O(n) time and O(n) for the result. Growing newInterval with min/max is O(1).
  4. Pitfall: the comparisons are strict. newInterval[1] < intervals[i][0] means a real gap; when they are equal ([2,4] and [4,6]) the intervals touch and must merge. Also handle the loop ending without a return: newInterval still has to be appended.
  5. Related: Merge Intervals (56) is the unsorted version; this is its one-pass special case.