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.

Restating the Problem: You have a perfectly organized schedule of non-overlapping events. Suddenly, a new event is added. Your job is to insert this new event into the schedule. If it overlaps with any existing events, you must merge them into one continuous block so that the final schedule remains conflict-free.

• Constraints to note: The number of intervals n is up to 10^4. They are already sorted, which is a massive hint to aim for an O(n) solution.
• Edge cases: The new interval might come completely before all others, completely after all others, or it might swallow all existing intervals entirely.

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]]

Brute Force Approach

A naive approach would be to simply append the newInterval to the end of the intervals array, and then run a standard "Merge Intervals" algorithm. This involves sorting the entire combined array, which takes O(n \log n) time. While O(n \log n) is acceptable for n=10^4, it completely ignores the fact that the initial array is already sorted. We can do better by doing it in a single pass.

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.

Code Walkthrough:

• Initialization: We prepare a result list and track our current index i. We also unpack start and end from the newInterval.
• Phase 1 (Before): We loop as long as the current interval ends before our new interval starts (intervals[i][1] < start). These are strictly earlier, so we append them directly to result.
• Phase 2 (Overlap): We loop as long as the current interval starts at or before our new interval ends (intervals[i][0] <= end). This means they overlap or touch. We continuously merge them by updating start to the minimum of both starts, and end to the maximum of both ends. Once this loop finishes, the fully expanded new interval is ready, and we append it to result.
• Phase 3 (After): We append any remaining intervals. Since they start strictly after our new interval ends, no further merging is needed.

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

• Time Complexity: O(n). Even though there are three while loops, the index i only moves forward and each interval is processed exactly once. Thus, the total work is strictly proportional to n.
• Space Complexity: O(n) to store the output array. No auxiliary space beyond variables is used.

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.