{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Insert Interval – Solution & Complexity

Interview solutions
/
Insert Interval

Solution Walkthrough

  1. Step 1: Understand the Goal

    • intervals arrives pre-sorted and non-overlapping, so the only disorder in the whole array comes from inserting newInterval once.
    • Because of that guarantee, you never need a general sort or an O(n^2) overlap check — a single left-to-right scan is enough to find exactly where the new interval lands.

  2. Step 2: Choose the Core Pattern

    • Split the array into three contiguous phases relative to newInterval: intervals that end strictly before it starts, intervals that overlap it, and intervals that start strictly after it ends.
    • "Overlap" here includes endpoint-touching intervals like [1,2] and [2,3] — treat <=/>= (not strict </>) as the overlap test, since a merged [1,3] is still a single valid interval and keeping [1,2],[2,3] separate would be a needlessly fragmented answer.

  3. Step 3: Build the Algorithm

    • Phase 1: while the current interval's end is strictly less than the new interval's start, it can't overlap — copy it through unchanged.
    • Phase 2: while the current interval's start is <= the new interval's end, they touch or overlap — absorb it by taking the min of starts and max of ends, growing newInterval in place rather than emitting anything yet.
    • After phase 2 ends (or immediately if it never ran), emit the now-final merged interval exactly once.
    • Phase 3: copy every remaining interval through unchanged — by definition none of them can touch the merged interval, since the scan already passed the last one that could.

  4. Step 4: Check Edge Cases

    • Empty intervals: phases 1 and 3 run zero times and phase 2 also runs zero times, so the result is just [newInterval].
    • newInterval fits entirely before the first interval or after the last: it participates in zero merges and is emitted as its own entry in the correct position.
    • newInterval fully contains one or more existing intervals: the min/max absorption in phase 2 naturally swallows them without special-casing containment separately from partial overlap.

  5. Step 5: Final Solution and Complexity

    • Time complexity is O(n).
    • Space complexity is O(n).
    def insert(intervals: list[list[int]], new_interval: list[int]) -> list[list[int]]:
    merged = []
    i = 0
    start, end = new_interval
    while i < len(intervals) and intervals[i][1] < start:
        merged.append(intervals[i])
        i += 1
    while i < len(intervals) and intervals[i][0] <= end:
        start = min(start, intervals[i][0])
        end = max(end, intervals[i][1])
        i += 1
    merged.append([start, end])
    while i < len(intervals):
        merged.append(intervals[i])
        i += 1
    return merged

FAQ

See also

Practice Insert Interval online (run code in the browser)Merge Intervals solution (medium)Non-overlapping Intervals solution (medium)3Sum solution (medium)3Sum Closest solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?