LeetCode Solutions Blog

Insert Interval

Number: 57

Difficulty: Medium

Paid? No

Problem Description

Insert a new interval into a sorted list of non-overlapping intervals such that the resulting intervals remain sorted and merged without any overlaps.

Key Insights

The intervals array is sorted by start times.
Three main steps are used:
1. Add intervals that come completely before the new interval.
2. Merge overlapping intervals with the new interval.
3. Append intervals that start after the new (merged) interval.
Iterating through the list once allows an O(n) solution.

Space and Time Complexity

Time Complexity: O(n) since we scan the list once. Space Complexity: O(n) to store the resulting list of intervals.

Solution

Traverse the intervals list and perform the following:

Append all intervals that end before the new interval starts.
For intervals that overlap with newInterval, update newInterval to merge them (using min for start and max for end).
Append the new merged interval.
Append all remaining intervals. This ensures that all intervals remain non-overlapping and sorted with a single pass.

Code Solutions

# Python solution for Insert Interval

class Solution:
    def insert(self, intervals, newInterval):
        # List to store the resulting intervals
        merged_intervals = []
        i = 0
        n = len(intervals)
        
        # Add all intervals that end before newInterval starts
        while i < n and intervals[i][1] < newInterval[0]:
            merged_intervals.append(intervals[i])
            i += 1
        
        # Merge overlapping intervals with newInterval
        while i < n and intervals[i][0] <= newInterval[1]:
            # Update the start and end of newInterval by merging with overlapping intervals
            newInterval[0] = min(newInterval[0], intervals[i][0])
            newInterval[1] = max(newInterval[1], intervals[i][1])
            i += 1
        # Add the merged newInterval
        merged_intervals.append(newInterval)
        
        # Add any remaining intervals that come after newInterval
        while i < n:
            merged_intervals.append(intervals[i])
            i += 1
        
        return merged_intervals