57. Insert Interval

Most interval problems make you sort first. Insert Interval is the one that hands you a sorted list up front — and the whole trick is noticing that this gift lets you skip the sort and finish in a single pass. It belongs to the interval patterns family, and it’s the cleanest place to see how “already sorted” changes the shape of the solution.

The problem

You’re given a list of intervals that’s already sorted by start and has no overlaps, plus one new interval to slot in. Return the list after inserting it, merging anything the newcomer collides with so the result stays sorted and overlap-free. (Full statement on LeetCode.)

Say the list is [[1,3], [6,9]] and you insert [2,5]. The new one overlaps [1,3], so they fuse into [1,5], and [6,9] rides along untouched: [[1,5], [6,9]].

Intuition: the list splits into three zones

Because the intervals are sorted and non-overlapping, the new interval carves the list into three consecutive stretches, and you never have to look back:

• Before — intervals that end before the new one even starts. They can’t touch it, so copy them as-is.
• Overlapping — intervals that start at or before the new interval ends. Every one of these gets swallowed. Keep stretching the new interval’s bounds to cover them.
• After — everything that starts past the new interval’s end. Untouched again, just copy the rest.

The middle zone is the only place any work happens. As you absorb each overlapping interval, you widen the newcomer:

$\text{lo} \leftarrow \min(\text{lo},\, s_i), \qquad \text{hi} \leftarrow \max(\text{hi},\, e_i)$

The boundary that separates “before” from “overlap” is where the < sits: an interval belongs to the before zone only when its end is strictly less than the new start. That makes touching intervals like [1,3] and [3,5] merge instead of staying apart — worth deciding out loud, since the problem treats a shared endpoint as an overlap.

Solution

One linear scan, three loops, no sorting. The pointer i walks forward exactly once across all three zones:

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

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

        // Zone 2: absorb every interval that overlaps, widening as we go
        while (i < n && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
            newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
            i++;
        }
        out.add(newInterval);   // add the (possibly stretched) merged interval once

        // Zone 3: everything that starts after the new interval ends
        while (i < n) {
            out.add(intervals[i++]);
        }

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

The two conditions carry the whole algorithm. Zone 1 stops the moment an interval reaches into the new one (end >= newStart); zone 2 stops the moment an interval starts past the new one (start > newEnd). Whatever’s left is zone 3 by definition.

Complexity

	Time	Space
Three-phase sweep	$O(n)$	$O(n)$

Each interval is visited once, so time is linear. The $O(n)$ space is just the output list — there’s no auxiliary bookkeeping beyond it.

In an interview

Lead by naming the gift: “the input is already sorted and non-overlapping, so I can split it into before / overlap / after and do one pass — no sort needed.” That single observation is what separates this from Merge Intervals, where the $O(n \log n)$ sort is unavoidable because the input is unordered.

The trap is the merge condition. Reach for < in zone 2 (instead of <=) and touching intervals silently fail to merge; forget to keep the min on the low end and a new interval that starts before an existing one loses ground it should have kept. Walk one example where the newcomer swallows several intervals at once — [[1,2],[3,5],[6,7],[8,10],[12,16]] inserting [4,8] collapses three of them into [3,10] — so the interviewer sees the widening actually work. Don’t forget the empty-list case: with n = 0 all three loops no-op and you just return the new interval alone.

If you enjoyed the sweep here, Non-overlapping Intervals uses the same sorted-scan idea but greedily drops intervals instead of merging them. Both live under the interval patterns hub.

References

• LeetCode 57 — Insert Interval