LeetCode 57 – Insert Interval | Love Me Some Coding

Insert Interval hands you something Merge Intervals had to earn: the list is already sorted and already non-overlapping. Every sentence of the problem statement that describes the input is a hint about the intended complexity, and the intended complexity here is O(n).

The problem

Given a list of non-overlapping intervals sorted by start, insert a new interval, merging where necessary. Return the result, still sorted and still non-overlapping.

[[1,3],[6,9]],            new = [2,5]   -> [[1,5],[6,9]]
[[1,2],[3,5],[6,7],[8,10],[12,16]],
                          new = [4,8]   -> [[1,2],[3,10],[12,16]]
[],                       new = [5,7]   -> [[5,7]]
[[1,5]],                  new = [2,3]   -> [[1,5]]      swallowed
[[1,5]],                  new = [6,8]   -> [[1,5],[6,8]]
[[1,5]],                  new = [5,7]   -> [[1,7]]      touching merges

The answer you should not give

Append the new interval, sort, run the merge from problem 56. It is three lines, it is correct, and it is O(n log n) on input that was handed to you sorted.

Say it — it proves you see the connection to the previous problem — and then immediately say why you are not doing it. Throwing away a precondition the problem went out of its way to give you is the thing being tested.

Three phases, in order

Because the input is sorted and disjoint, the intervals fall into three consecutive groups, and you can walk them with one index and never look back.

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

  [1,2]                     ends before 4 starts       copy through
  [3,5] [6,7] [8,10]        touch [4,8]                absorb: [3,10]
  [12,16]                   starts after 10            copy through

Before. Everything ending strictly before the new interval starts is emitted untouched.
Overlapping. Everything that touches the new interval is swallowed into it, widening it on both sides: start = min(...), end = max(...). Emit the widened interval once, after the group is exhausted.
After. The rest is emitted untouched.

The min in phase 2 is easy to skip. The new interval can start before an interval it overlaps — [[3,5]] with [4,8] gives [3,8], and the 3 came from the list, not from the new interval.

The two comparisons are the whole problem

phase 1 continues while   intervals[i].end < start
phase 2 continues while   intervals[i].start <= end

Both boundaries are chosen so touching intervals merge. If intervals[i].end == start they touch, so phase 1 must stop and let phase 2 absorb it — hence strict <. If intervals[i].start == end they touch, so phase 2 must take it — hence <=. Flip either one and [[1,5]] with [5,7] returns two intervals instead of one.

The end in the phase 2 test is the running end, re-read on every iteration, not the new interval's original end. That is what lets one insertion swallow a chain: with [[1,2],[3,10]] and a new interval of [2,4], absorbing [1,2] then [3,10] pushes the end out to 10, and it is the widened value that each subsequent comparison uses. Capture end up front and the chain stops after one link.

Java

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> out = new ArrayList<>();
        int start = newInterval[0], end = newInterval[1];
        int i = 0, n = intervals.length;

        // 1. everything that ends before the new interval begins
        while (i < n && intervals[i][1] < start) {
            out.add(intervals[i]);
            i++;
        }

        // 2. everything that touches it, absorbed into one widened interval
        while (i < n && intervals[i][0] <= end) {
            start = Math.min(start, intervals[i][0]);   // the new one may start later
            end = Math.max(end, intervals[i][1]);       // ...and end earlier
            i++;
        }
        out.add(new int[]{start, end});

        // 3. the rest, untouched
        while (i < n) {
            out.add(intervals[i]);
            i++;
        }

        return out.toArray(new int[out.size()][]);
    }
}

Three sequential while loops sharing one index, and no if statements at all. That is worth aiming for deliberately: the version people write first is a single loop with a three-way branch inside it, and it is where the off-by-one bugs live. Splitting the phases makes each condition answerable on its own.

Unlike Merge Intervals, the pass-through intervals are added by reference and never written to, so no defensive copy is needed. The one interval that is constructed is the merged one, which is new memory.

Python

class Solution:
    def insert(self, intervals: list[list[int]], newInterval: list[int]) -> list[list[int]]:
        out: list[list[int]] = []
        start, end = newInterval
        i, n = 0, len(intervals)

        while i < n and intervals[i][1] < start:      # ends before it begins
            out.append(intervals[i])
            i += 1

        while i < n and intervals[i][0] <= end:       # overlaps or touches
            start = min(start, intervals[i][0])
            end = max(end, intervals[i][1])
            i += 1
        out.append([start, end])

        out.extend(intervals[i:])                    # the rest
        return out

out.extend(intervals[i:]) replaces the third loop, and the empty-input case falls out for free: both while loops fail immediately, the new interval is appended, and the slice is empty.

Complexity

Approach	Time	Space
Append, sort, merge	`O(n log n)`	`O(n)`
Three-phase scan	`O(n)`	`O(n)` output only

Each interval is visited exactly once, by exactly one of the three loops — the shared i guarantees it. Output space is unavoidable since the result is a new array; ignoring the output, the scan is O(1).

The follow-up worth anticipating

Phase 1 is a scan for the first interval whose end reaches start, over a sorted array — so it can be a binary search, and so can the end of phase 2. That makes the search O(log n)… and the copying still O(n), so the overall bound does not move.

Say exactly that. "Binary search finds the boundaries in O(log n), but we copy the tail anyway, so it stays O(n)" is a much better answer than either implementing it without noticing or not seeing it at all. It becomes a real win only if the structure supports splicing rather than copying — a balanced BST or a skip list — which is the door into the "design an interval store" system-design version of this question.

What the interviewer is checking

That you notice the input is pre-sorted and refuse to re-sort it.
The three phases, with one index shared across them.
min as well as max when absorbing — the new interval is not necessarily the leftmost.
< in phase 1 and <= in phase 2, so touching intervals merge.
Empty input, insertion before everything, insertion after everything.
An insert that swallows several intervals at once.
That you can spot the binary-search refinement and say why it does not change the complexity.