Skip to main content
DSA patterns

Insert Interval

mediumIntervals Must-doAWSGCPAzure

Problem statement

You're given a list of intervals, intervals, that don't overlap each other and are already sorted by their start value — think of them as existing maintenance windows or deployment freezes on a shared calendar. You're also given one more interval, newInterval, that needs to be added to that calendar.

Two intervals overlap if they share even a single point in time (so [1, 3] and [3, 5] count as overlapping, since they both touch 3).

Insert newInterval into intervals so the list stays sorted by start value and still has no overlaps — merging any intervals that touch or overlap newInterval into one combined interval. Return the resulting list. You don't have to modify intervals in place; returning a new list is fine.

Examples

Example 1

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

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

Explanation: newInterval = [2, 5] overlaps [1, 3] (they share the point 3), so they merge into [1, 5]. It doesn't touch [6, 9] at all, so that interval is unchanged.

Example 2

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

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

Explanation: [4, 8] overlaps [3, 5], [6, 7] and [8, 10] — it touches or crosses all three — so they merge together into one interval, [3, 10]. [1, 2] ends before 4, and [12, 16] starts after 10, so neither is touched.

Hints

Hint 1: Every existing interval falls into exactly one of three groups relative to newInterval: it ends before newInterval starts, it starts after newInterval ends, or it overlaps and needs merging.

Approach

Optimal: Three-phase single pass

Intuition

intervals is already sorted and non-overlapping, so there's no need to sort anything — that guarantee can be used directly. Split the work into three phases in a single pass: first copy every interval that ends before newInterval even starts straight into the result, since those can never overlap it. Then, for as long as the next interval's start is still within newInterval's current end, merge it in by growing newInterval's own start and end to cover it — this sweeps up every overlapping interval in one go. Once that stops, push the (possibly grown) newInterval into the result. Finally, copy whatever intervals are left — they all start after newInterval ends, so none of them can overlap it either.

Steps

  1. Start an empty result list, an index i = 0, and start, end set to newInterval's own start and end.
  2. While i < n and intervals[i]'s end is before start: this interval can't overlap newInterval — push it to the result and advance i.
  3. While i < n and intervals[i]'s start is ≤ end: this interval overlaps — grow start to the smaller of the two starts and end to the larger of the two ends, then advance i.
  4. Push the interval [start, end] (now covering everything it merged with) to the result.
  5. While i < n: these intervals all start after end — push each one to the result as-is and advance i.
  6. Return the result.

Dry run

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

phase i interval condition action
before 0 [1,2] 2 < 4 push [1,2], i=1
before 1 [3,5] 5 < 4? no stop "before" phase
merge 1 [3,5] 3 ≤ 8 start=min(4,3)=3, end=max(8,5)=8, i=2
merge 2 [6,7] 6 ≤ 8 start=3, end=max(8,7)=8, i=3
merge 3 [8,10] 8 ≤ 8 start=3, end=max(8,10)=10, i=4
merge 4 [12,16] 12 ≤ 10? no stop "merge" phase → push [3,10]
after 4 [12,16] — push [12,16], i=5

Result: [[1,2],[3,10],[12,16]], matching Example 2.

Edge cases: an empty intervals list means both the "before" and "merge" loops never run (n = 0), so the result is simply [newInterval]. If newInterval starts after every existing interval ends, the "merge" loop never runs either, and newInterval is pushed on its own after all the existing intervals.

Complexity

Time O(n) - one pass through `intervals`, no sorting.

Space O(n) - for the output list; O(1) extra beyond that.

from typing import List


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

        while i < n and intervals[i][1] < start:
            result.append(intervals[i])
            i += 1

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

        while i < n:
            result.append(intervals[i])
            i += 1

        return result


if __name__ == "__main__":
    print(Solution().insert([[1, 3], [6, 9]], [2, 5]))  # [[1, 5], [6, 9]]
    print(Solution().insert([[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], [4, 8]))  # [[1, 2], [3, 10], [12, 16]]
RecapThe whole problem in a few lines, for the night before
  • Spot it: "insert one interval into an already-sorted, non-overlapping list and merge anything it touches"
  • Idea: copy every interval fully before the new one, merge everything that overlaps it by growing the new interval's own bounds, then copy the rest — one linear pass, no sorting needed
  • Cost: O(n) time, O(n) space for the output
  • Trap: using < instead of <= in the overlap check misses intervals that only touch at a shared endpoint, since the problem counts that as overlapping

Interview follow-ups

  • What if you needed to insert many new intervals, one after another?

    Repeating this O(n) insert once per new interval costs O(n·m) total for m insertions. If all m new intervals are known upfront, it's usually cheaper to append all of them to the list, sort once — O((n+m) log(n+m)) — and merge everything in a single pass, trading away the "no sort needed" advantage of a single insert for the benefit of batching.

  • How would you support fast overlap checks on a huge, frequently-changing set of intervals?

    Keep the intervals in a structure ordered by start that supports fast search and insert, such as a balanced tree or an interval tree, so a single insert or overlap query costs O(log n) instead of scanning the whole list. The trade-off is extra bookkeeping to keep that structure balanced as intervals are added and removed over time.

Frequently asked questions

Because intervals is already guaranteed sorted by start and non-overlapping — that's given in the problem, not something you have to establish. The brute-force approach only sorts because it throws that guarantee away and rebuilds the order from scratch, which is more general but wasted work here.

It means two intervals like [1, 3] and [3, 5] count as overlapping, not just touching, so both approaches use <= in their merge check (start <= current end, or intervals[i][0] <= end) rather than <. Using < instead would leave two intervals that only share an endpoint unmerged, which the problem doesn't allow.

It's the same shape as inserting a new maintenance window, deployment freeze, or resource reservation into an already-sorted schedule and merging it with anything it overlaps, so the calendar never ends up double-booked at any point in time.

The "before" and "after" phases would both do nothing — there's nothing that ends before newInterval starts, and nothing left over once the merge is done — while the merge phase would sweep through the whole list, and the result would be a single interval covering everything.