4.27.1 — Insert Interval

LeetCode 57 · Medium · ★ Blind 75

The problem

Given a list of non-overlapping intervals sorted by start, insert a new interval and merge where necessary. The result must stay sorted and non-overlapping.

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

The pattern

The input is already sorted, which is the gift — no sorting step, so this is O(n) rather than O(n \log n).

Walk the list once, and every interval falls into exactly one of three groups:

1. Ends before the new one starts — no overlap, copy it out.
2. Overlaps the new one — absorb it into the new interval by widening.
3. Starts after the new one ends — no overlap, copy it out.

Because the list is sorted, the three groups appear in exactly that order, so three sequential loops handle them with no conditionals inside.

The overlap test

Two intervals [a, b] and [c, d] overlap when:

a \le d \ \text{and}\ c \le b

Each starts before the other ends. Worth memorising in that form, because it is the cleanest statement and it generalises.

It is often easier to test the negation: they do not overlap when b < c or d < a — one finishes entirely before the other begins. That is what the first and third loops below check.

Touching counts as overlapping here. [1,3] and [3,5] merge into [1,5], because the problem treats them as adjacent. Some problems do not — always check, because it decides whether the comparison is < or <=.

The solution

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

        # 1. everything entirely before the new interval
        while i < n and intervals[i][1] < start:
            result.append(intervals[i])
            i += 1

        # 2. everything that overlaps — widen the new interval to swallow it
        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])

        # 3. everything entirely after
        while i < n:
            result.append(intervals[i])
            i += 1

        return result

TypeScript

function insert(intervals: number[][], newInterval: number[]): number[][] {
  const result: number[][] = [];
  let i = 0;
  const n = intervals.length;
  let [start, end] = newInterval;

  while (i < n && intervals[i][1] < start) result.push(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.push([start, end]);

  while (i < n) result.push(intervals[i++]);

  return result;
}

Three loops, no branching. Each loop handles one group, and the sorted order guarantees they run in sequence. Trying to do it in one loop with an if/elif/else is possible and much harder to keep straight.

The merged interval is appended after the second loop, not inside it — you only know its final extent once every overlapping interval has been absorbed.

intervals[i][0] <= end uses <= because touching intervals merge here.

The new interval is appended even if nothing overlapped, which is what handles insertion into a gap.

Trace

intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], new [4,8].

• Loop 1: [1,2] ends at 2 < 4 → copied.
• Loop 2: [3,5] starts at 3 ≤ 8 → merge, now [3,8]. [6,7] starts at 6 ≤ 8 → merge, still [3,8]. [8,10] starts at 8 ≤ 8 → merge, now [3,10]. [12,16] starts at 12 > 10 → stop.
• Append [3,10].
• Loop 3: [12,16] copied.

Result [[1,2],[3,10],[12,16]] ✓.

Complexity

O(n) time, O(n) space for the output.

Compare with the alternative of appending the new interval, re-sorting, and merging — O(n \log n). The sorted input is what buys the linear time, and saying so shows you noticed the constraint.

Where this goes next

• Merge Intervals — no new interval, but the input is unsorted, so you sort first and then run the same merging loop. 4.27.2.
• Interval List Intersections — two sorted lists, walked with two pointers, keeping the overlap of each pair.
• Calendar booking (LeetCode 729, 731, 732) — repeated insertions with overlap rules, where a balanced tree or an ordered map keeps each insertion O(\log n) instead of O(n). That is the natural follow-up when insertions are frequent.

What the interviewer will push on

"State the overlap condition." a <= d and c <= b. Have it ready.

"Do touching intervals merge?" Ask. It changes < to <=, and it is a genuine ambiguity in most problem statements.

"Why three loops?" The sorted order puts the three groups in sequence, so no interleaved conditionals are needed.

"Why is this O(n) and Merge Intervals O(n \log n)?" The input here is already sorted.

"What if you had to insert many intervals?" Repeated O(n) insertions become O(nk). Switch to an ordered map or a balanced tree for O(\log n) per insertion.

One thing to volunteer: name the three groups before writing anything. This problem is easy with the structure stated and fiddly without it.

Next: 4.27.2 Merge Intervals — the same merging, with the sort you have to add yourself.