How do you approach Insert Interval?

Think in three phases: intervals entirely BEFORE the new one, intervals that OVERLAP it, intervals entirely AFTER.

What is the optimal solution to Insert Interval?

Three phases, one pass. Because the input is sorted and non-overlapping, the intervals split cleanly into three consecutive groups, and you can handle each in order: Strictly before - interval.end < newInterval.start. These can never touch the new interval; copy them out unchanged. Overlapping - everything with interval.start <= newInterval.end.

What is the time complexity of Insert Interval?

Time complexity: O(n). Space complexity: O(n) for the output..

What are common mistakes on Insert Interval?

Not sorting first. Nearly every interval algorithm assumes the list is ordered by start, and skipping that step gives answers that are right on the sample and wrong everywhere else. Treating touching intervals as overlapping (or not) without checking which the problem means. Mutating the input intervals while iterating over them.

Sitelet https://gitgood.dev/coding/insert-interval

gitGood.dev

← Back to problems

Insert Interval

MediumAlgorithms

Description

You are given a list of non-overlapping intervals sorted by start time, and a newInterval to insert.

Insert it so the list stays sorted and non-overlapping, merging with any intervals it touches or overlaps. Return the resulting list.

Because the input is already sorted, you should not need to sort anything - a single pass is enough.

Example 1

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]

Output: [[1,5],[6,9]]

Example 2

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

Output: [[1,2],[3,10],[12,16]]

Example 3

Input: intervals = [], newInterval = [5,7]

Output: [[5,7]]

Constraints

- 0 <= intervals.length <= 10^4 - intervals is sorted by start and contains no overlaps - 0 <= start <= end <= 10^5 - Solve in O(n) without sorting.

Insert Interval: approach, complexity and pitfalls

A medium intervals problem, graded against 6 test cases (3 of them hidden).

The pattern: Intervals

Sorting by start or end, then merging or scheduling overlapping ranges.

Reach for it when you see: Meetings, bookings, ranges, or anything with a start and an end.

If you are stuck

Show the 3-step hint ladder

Think in three phases: intervals entirely BEFORE the new one, intervals that OVERLAP it, intervals entirely AFTER.
Phase 1: copy while interval.end < newInterval.start. Phase 3: copy the rest once you are past the overlap.
Phase 2: while interval.start <= newInterval.end, absorb it by widening newInterval to min(starts) and max(ends). Push the widened interval once, between the two copy phases.

The optimal approach

Show the approach: Three phases, one pass

Because the input is sorted and non-overlapping, the intervals split cleanly into three consecutive groups, and you can handle each in order:

1. Strictly before - `interval.end < newInterval.start`. These can never touch the new interval; copy them out unchanged.

2. Overlapping - everything with `interval.start <= newInterval.end`. Rather than emitting these, absorb them: widen the new interval to `min(starts)` and `max(ends)`. When the loop ends, push the widened interval exactly once.

3. Strictly after - copy the remainder unchanged.

The comparisons are where this goes wrong. Both boundary tests use non-strict logic against the *other* endpoint, so intervals that merely touch (`[1,3]` and `[3,5]`) merge rather than being emitted separately - matching the usual convention for this problem, and the opposite of the meeting-rooms convention. It is worth confirming which one the interviewer wants.

No sort is needed, so this beats the merge-intervals approach of appending and re-sorting.

Time: O(n)
Space: O(n) for the output.

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty input. At least one case passes an empty collection. Make sure your loop bounds and any "first element" read survive a length of zero.
Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.

Common Intervals mistakes

These apply to the pattern as a whole, not just this problem.

Not sorting first. Nearly every interval algorithm assumes the list is ordered by start, and skipping that step gives answers that are right on the sample and wrong everywhere else.
Treating touching intervals as overlapping (or not) without checking which the problem means.
Mutating the input intervals while iterating over them.