Big O Practice: Insert Interval

def insert(intervals, new_interval):
    res = []
    n = len(intervals)
    i = 0
    # intervals strictly before the new one
    while i < n and intervals[i][1] < new_interval[0]:
        res.append(intervals[i])
        i += 1
    # merge overlapping intervals
    lo, hi = new_interval
    while i < n and intervals[i][0] <= hi:
        lo = min(lo, intervals[i][0])
        hi = max(hi, intervals[i][1])
        i += 1
    res.append([lo, hi])
    while i < n:
        res.append(intervals[i])
        i += 1
    return res

Variables

• n - number of input intervals

Explanation

A single sweep over already-sorted intervals - **O(n)** time. The result list holds up to `n + 1` intervals, **O(n)** space. No sorting needed because the input is sorted by hypothesis.

More Big O practice problems · Today's daily problem