Insert Interval

Medium

Insert Interval

Medium

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Are the given intervals guaranteed to be sorted by their start times?
Can the input intervals overlap, and if so, how should overlapping intervals be handled?
Can the new interval overlap with multiple existing intervals, and how should the merged result be?
Are the start and end times of the intervals integers? Can they be negative?
What should be returned if the input list of intervals is empty?

Brute Force Solution

Approach

We have a set of existing time intervals and a new time interval to insert into the set. The brute force approach involves going through all possibilities of how the new interval can fit within the existing set, checking overlaps and merging as needed.

Here's how the algorithm would work step-by-step:

First, add the new time interval into the existing list of intervals. Now you have one big, unsorted list.
Next, sort the list of time intervals from earliest to latest.
Now go through the sorted list from the beginning.
For each interval, check if it overlaps with the next interval.
If two intervals overlap, merge them into a single, bigger interval.
Keep checking and merging until no intervals overlap anymore.
The remaining intervals are the final, non-overlapping set with the new interval inserted.

Code Implementation

def insert_interval_brute_force(existing_intervals, new_interval):
    # Add the new interval to the list
    combined_intervals = existing_intervals + [new_interval]

    # Sort the intervals based on start time
    combined_intervals.sort(key=lambda interval: interval[0])

    merged_intervals = []
    index = 0

    while index < len(combined_intervals):
        current_interval = combined_intervals[index]
        # Start by assuming no overlap
        while index + 1 < len(combined_intervals) and \
                current_interval[1] >= combined_intervals[index + 1][0]:
            next_interval = combined_intervals[index + 1]
            # Perform the merge
            current_interval = [min(current_interval[0], next_interval[0]), \
                                max(current_interval[1], next_interval[1])]
            index += 1

        merged_intervals.append(current_interval)
        index += 1

    return merged_intervals

Big(O) Analysis

Time Complexity

O(n log n) – The dominant operation is sorting the list of intervals, which takes O(n log n) time, where n is the total number of intervals after insertion. The subsequent merging process involves iterating through the sorted list, checking for overlaps, and merging intervals. While this merging step might appear to be O(n^2) in a worst case scenario if every interval overlaps with the next one, the act of merging reduces the size of the overall interval list, such that the merging process is still upper bounded by O(n). Therefore, the O(n log n) sorting step is the most time consuming, making the overall time complexity O(n log n).

Space Complexity

O(N) – The algorithm first adds the new interval to the existing list of intervals, potentially creating a new list of size N+1 (where N is the original number of intervals). Sorting this combined list generally requires O(N) auxiliary space, depending on the sorting algorithm used (e.g., merge sort). While the merging process itself might happen in-place in some implementations, many sorting algorithms require extra space for temporary storage during the sort. Therefore, the dominant factor is the sorting, leading to O(N) space complexity.

Optimal Solution

Approach

The optimal approach avoids needlessly comparing the new interval with every existing interval. It breaks down the task into three clear stages: adding intervals that come completely before the new one, merging overlapping intervals, and adding intervals that come completely after the new one.

Here's how the algorithm would work step-by-step:

First, add all the existing intervals that end before the new interval starts. These intervals don't overlap and remain unchanged.
Next, merge the new interval with any existing intervals that overlap it. Keep combining intervals until you find one that doesn't overlap.
Finally, add the remaining intervals that start after the new interval ends. These intervals also don't overlap and stay as they are.
The result is a new list of intervals with the new interval correctly inserted and merged, avoiding unnecessary comparisons.

Code Implementation

def insert_interval(existing_intervals, new_interval):
    merged_intervals = []
    interval_index = 0

    # Add all intervals ending before the new interval.
    while interval_index < len(existing_intervals) and existing_intervals[interval_index][1] < new_interval[0]:
        merged_intervals.append(existing_intervals[interval_index])
        interval_index += 1

    # Merge overlapping intervals.
    while interval_index < len(existing_intervals) and existing_intervals[interval_index][0] <= new_interval[1]:
        # Adjust the new interval to encompass the overlapping interval.
        new_interval[0] = min(new_interval[0], existing_intervals[interval_index][0])
        new_interval[1] = max(new_interval[1], existing_intervals[interval_index][1])
        interval_index += 1

    merged_intervals.append(new_interval)

    # Add all remaining intervals.
    while interval_index < len(existing_intervals):
        # Add the rest of the intervals as they do not overlap.
        merged_intervals.append(existing_intervals[interval_index])
        interval_index += 1

    return merged_intervals

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the existing intervals list once. In the first stage, it appends intervals that come before the new interval. In the second stage, it merges overlapping intervals, potentially iterating through a portion of the list. In the third stage, it appends the remaining intervals that come after the new interval. Overall, each interval is visited at most a constant number of times, resulting in a linear time complexity of O(n), where n is the number of intervals.

Space Complexity

O(N) – The algorithm creates a new list to store the merged intervals. In the worst-case scenario, where the new interval doesn't overlap with any existing intervals, the new list will contain all the original intervals plus the new interval, resulting in N+1 intervals. Therefore, the auxiliary space required scales linearly with the number of intervals in the input. This results in O(N) space complexity.

Edge Cases

Case	How to Handle
Empty intervals array	If the intervals array is empty, return the new interval as the only element in the resulting array.
Null intervals array or new interval	Throw an IllegalArgumentException or return null to indicate invalid input.
New interval completely before all existing intervals	Insert the new interval at the beginning of the result list.
New interval completely after all existing intervals	Append the new interval at the end of the result list.
New interval overlaps with multiple existing intervals.	Merge all overlapping intervals into a single, larger merged interval.
New interval is contained entirely within an existing interval	The existing interval remains unchanged in the resulting array as there is no merging required.
New interval is identical to an existing interval.	The new interval will merge with the existing, with the result equivalent to the original interval, so no change is needed.
Large input size (many intervals)	Ensure the algorithm has linear time complexity and does not use excessive memory, which might require optimization of operations like list insertions and deletions.