Insert Interval: Multiple Solutions and Complexity Analysis

Understanding the Insert Interval Problem

The Insert Interval problem is a classic algorithmic challenge that appears frequently in coding interviews and real‑world software development. You are given a list of non‑overlapping intervals sorted by their start times, and a new interval to insert. The goal is to insert the new interval into the list and merge any overlapping intervals, returning the resulting list in sorted order without any overlaps.

Formally, each interval is represented as a pair [start, end]. The input list intervals is sorted by start and contains no overlapping intervals. You receive newInterval = [start, end]. You must return a new list of intervals that covers all the same points but with no overlaps.

Why This Problem Matters

Interval insertion and merging are foundational operations in many domains. Practical applications include:

• Calendar scheduling: adding a new event and resolving conflicts.
• Database range queries: combining disjoint index ranges after an update.
• Video timeline editing: inserting a clip into an existing track and merging overlapping segments.
• Network bandwidth allocation: merging time windows when a new reservation arrives.

Mastering multiple solutions to this problem deepens your understanding of interval logic, algorithm design, and complexity trade‑offs. It also builds intuition for handling sorted data and in‑place vs. out‑of‑place modifications.

Solution 1: Three‑Phase Linear Scan

The most intuitive approach divides the work into three sequential phases:

• Phase 1: Append all intervals that end before the new interval starts. They cannot overlap.
• Phase 2: Merge the new interval with all overlapping intervals. Keep expanding the new interval’s boundaries as long as an interval starts before or at the current merged end.
• Phase 3: Append all remaining intervals that start after the merged interval ends.

This yields a clean, easy‑to‑reason‑about implementation.

def insert_three_phase(intervals, newInterval):
    # Handle empty input
    if not intervals:
        return [newInterval]

    result = []
    i = 0
    n = len(intervals)

    # Phase 1: add all intervals ending before newInterval starts
    while i < n and intervals[i][1] < newInterval[0]:
        result.append(intervals[i])
        i += 1

    # Phase 2: merge overlapping intervals with newInterval
    merged_start = newInterval[0]
    merged_end = newInterval[1]
    while i < n and intervals[i][0] <= merged_end:
        merged_start = min(merged_start, intervals[i][0])
        merged_end = max(merged_end, intervals[i][1])
        i += 1
    result.append([merged_start, merged_end])

    # Phase 3: add remaining intervals
    while i < n:
        result.append(intervals[i])
        i += 1

    return result

Time Complexity: O(n) – we traverse the list once. Space Complexity: O(n) for the output list (or O(1) if we don't count the result).

Solution 2: Single‑Pass Merging with a While Loop

You can combine the phases into a single pass using a more compact loop. The idea is to iterate through the intervals, deciding at each step whether to add the current interval, merge it with the pending new interval, or finally insert the merged interval and switch to simply copying the rest.

This version is slightly less explicit but reduces code duplication.

def insert_single_pass(intervals, newInterval):
    result = []
    i = 0
    n = len(intervals)

    # Insert intervals before the new interval (no overlap)
    while i < n and intervals[i][1] < newInterval[0]:
        result.append(intervals[i])
        i += 1

    # Now intervals[i] might overlap. Merge all overlapping ones.
    merged = newInterval[:]
    while i < n and intervals[i][0] <= merged[1]:
        merged[0] = min(merged[0], intervals[i][0])
        merged[1] = max(merged[1], intervals[i][1])
        i += 1
    result.append(merged)

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

    return result

Note that this is essentially the same as Solution 1, just presented as a single function with the merging logic embedded. It still runs in O(n) time and O(n) space.

Solution 3: Binary Search for Insertion Point

Because the input list is sorted, we can use binary search to locate where the new interval should be inserted. This reduces the search for the insertion index from O(n) to O(log n). However, building the final merged list still requires O(n) time because we may need to copy all elements (or merge a large chunk). The overall time remains O(n) due to the linear cost of list construction.

This approach is educational and demonstrates how binary search can be leveraged even when the overall complexity doesn't change.

import bisect

def insert_binary_search(intervals, newInterval):
    if not intervals:
        return [newInterval]

    # Extract start times for binary search
    starts = [iv[0] for iv in intervals]
    # Find the rightmost index where interval starts are <= newInterval[0]
    idx = bisect.bisect_right(starts, newInterval[0]) - 1

    # Now we must merge from idx (or 0) to wherever overlapping ends
    result = []
    i = 0
    n = len(intervals)

    # Add intervals before the merge zone (those completely before newInterval)
    while i < n and intervals[i][1] < newInterval[0]:
        result.append(intervals[i])
        i += 1

    # Merge overlapping intervals
    merged_start = newInterval[0]
    merged_end = newInterval[1]
    while i < n and intervals[i][0] <= merged_end:
        merged_start = min(merged_start, intervals[i][0])
        merged_end = max(merged_end, intervals[i][1])
        i += 1
    result.append([merged_start, merged_end])

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

    return result

Note: The binary search helps us find a starting index, but we still have to iterate forward to merge and copy. The worst‑case time remains O(n) because merging might touch all intervals.

Complexity Analysis Summary

All three solutions share the same asymptotic complexity:

• Time Complexity: O(n) – we perform a single linear scan (or a scan after binary search that still touches up to n elements).
• Space Complexity: O(n) – we create a new list to hold the result. In‑place modification is possible but typically avoided to preserve the input.

The binary search variant reduces the number of comparisons for finding the insertion point, but the dominant cost remains the linear merge phase. In practice, the constant factors are small and the code is straightforward.

Best Practices and Edge Cases

When implementing an interval insertion routine, keep these best practices in mind:

• Handle empty input: Always check if intervals is empty and return [newInterval] immediately.
• Define overlap clearly: Two intervals [a,b] and [c,d] overlap if a <= d and c <= b. In sorted order, the condition simplifies: the current interval’s start is ≤ the merged end.
• Use meaningful variable names: merged_start and merged_end make the merge logic self‑documenting.
• Consider immutability: Return a new list instead of modifying the input to avoid side effects, unless explicitly required.
• Test boundary cases:
  • New interval completely before all existing intervals.
  • New interval completely after all existing intervals.
  • New interval overlapping multiple intervals and extending beyond them.
  • New interval exactly matching an existing interval’s boundaries.
• Avoid off‑by‑one errors: Be precise with < vs <= when checking intervals[i][1] < newInterval[0] (no overlap) and intervals[i][0] <= merged_end (overlap condition).

Conclusion

The Insert Interval problem is a deceptively simple yet powerful exercise in interval manipulation. The standard O(n) linear scan remains the optimal and most readable solution. Variations like the single‑pass loop and binary‑search‑assisted insertion illustrate different ways to structure the logic while preserving the same complexity class.

By mastering these approaches, you gain a reusable pattern for merging time ranges, calendar events, and any sorted disjoint data. Focus on clarity, handle edge cases meticulously, and always prefer returning a new collection to keep your functions pure and predictable.