#57

Medium

auto_awesomeArray-driven solution strategy

LeetCode Problem Workspace

Insert Interval

Given a sorted array of non-overlapping intervals, insert a new interval and merge any overlapping intervals.

Problem Statement

You are given a sorted array of non-overlapping intervals, where each interval is represented as [start, end]. Additionally, you are provided with a new interval [start, end] to insert into the array. Your task is to insert this new interval into the existing sorted array of intervals while ensuring there are no overlapping intervals.

After inserting the new interval, you must merge any overlapping intervals to maintain the sorted order. Return the updated list of intervals after the insertion and merging process is complete.

Examples

Example 1

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]

Output: [[1,5],[6,9]]

Example details omitted.

Example 2

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]

Output: [[1,2],[3,10],[12,16]]

Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

Constraints

0 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 105
intervals is sorted by starti in ascending order.
newInterval.length == 2
0 <= start <= end <= 105

Solution Approach

Finding the Insertion Point

To efficiently insert the new interval, first find the correct position in the array using a binary search approach. This reduces the complexity of finding where the new interval fits within the existing intervals, especially when dealing with large inputs.

Merging Overlapping Intervals

Once the new interval is inserted, iterate through the intervals to merge any overlapping ones. Compare the current interval with the next, and if they overlap, merge them into a single interval. This step is key to maintaining the sorted order of the array.

Returning the Result

After completing the insertion and merging process, return the updated list of intervals. Ensure that no interval overlaps and that all intervals remain sorted in ascending order based on their start value.

Complexity Analysis

Metric	Value
Time	O(N)
Space	O(N)

The time complexity of this solution is O(N) where N is the number of intervals, due to the need to iterate through the array to merge intervals. The space complexity is O(N) as we might need to store a modified version of the intervals array in the worst case.

What Interviewers Usually Probe

Look for efficiency in finding the insertion point, particularly using binary search for the best performance.
Evaluate the candidate's understanding of merging intervals and their ability to handle edge cases such as no overlaps or full array merges.
Assess the candidate's grasp of time and space complexity analysis, especially in terms of managing large inputs.

Common Pitfalls or Variants

Common pitfalls

Failing to consider edge cases such as inserting an interval that doesn't overlap with any existing ones.
Not merging overlapping intervals correctly, which might leave the array unsorted or with unnecessary intervals.
Overcomplicating the solution with unnecessary data structures, making it more complex than needed.

Follow-up variants

Handling intervals that are already merged or include no overlaps at all.
Working with unsorted intervals before insertion, requiring an initial sorting step.
Inserting multiple intervals at once instead of just one new interval.

FAQ

How do I solve the Insert Interval problem efficiently?

Use binary search to find the appropriate position for the new interval and then merge any overlapping intervals in linear time.

What is the time complexity of the Insert Interval problem?

The time complexity is O(N) due to the need to merge intervals after insertion, where N is the number of intervals.

How can I handle multiple overlapping intervals during insertion?

Iterate through the intervals after inserting the new one and merge any that overlap by comparing their start and end values.

Why is binary search used in the Insert Interval problem?

Binary search helps efficiently find the correct position for the new interval, reducing the time complexity of the solution.

What are some common mistakes in solving the Insert Interval problem?

Common mistakes include failing to merge overlapping intervals correctly or not using efficient methods like binary search for finding the insertion point.

terminal

Solution

Solution 1: Sorting + Interval Merging

We can first add the new interval `newInterval` to the interval list `intervals`, and then merge according to the regular method of interval merging.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def insert(
        self, intervals: List[List[int]], newInterval: List[int]
    ) -> List[List[int]]:
        def merge(intervals: List[List[int]]) -> List[List[int]]:
            intervals.sort()
            ans = [intervals[0]]
            for s, e in intervals[1:]:
                if ans[-1][1] < s:
                    ans.append([s, e])
                else:
                    ans[-1][1] = max(ans[-1][1], e)
            return ans

        intervals.append(newInterval)
        return merge(intervals)

Solution 2: One-pass Traversal

We can traverse the interval list `intervals`, let the current interval be `interval`, and there are three situations for each interval:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def insert(
        self, intervals: List[List[int]], newInterval: List[int]
    ) -> List[List[int]]:
        def merge(intervals: List[List[int]]) -> List[List[int]]:
            intervals.sort()
            ans = [intervals[0]]
            for s, e in intervals[1:]:
                if ans[-1][1] < s:
                    ans.append([s, e])
                else:
                    ans[-1][1] = max(ans[-1][1], e)
            return ans

        intervals.append(newInterval)
        return merge(intervals)

Continue Practicing

#56 merge intervals #55 jump game #59 spiral matrix ii