MediumArrayIntervals

Insert Interval

1 approach, code in every language

You start with a list of non-overlapping intervals that is already ordered by start value. A single new interval arrives, and you must slot it into the list so that the final collection stays sorted and free of overlaps, merging with any existing intervals that it touches.

Return the updated list. Because the original data is presorted, a full re-sort is unnecessary; a single linear pass can place and merge the newcomer.

Example 1

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

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

The new range 2-5 overlaps 1-3, so they fuse into 1-5 while 6-9 stays untouched.

Example 2

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

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

4-8 spans 3-5, 6-7 and 8-10, collapsing all three into 3-10.

Constraints

0 ≤ intervals.length ≤ 10^4
intervals[i].length == 2 and newInterval.length == 2
0 ≤ start ≤ end ≤ 10^5
intervals is sorted by start in ascending order with no overlaps

Three-phase linear scan

Copy intervals that finish before the new one begins, absorb every interval that overlaps the new one, then copy the rest.

Loading animation…

Intuition

Since the list is already sorted and gap-free, every interval falls into exactly one of three buckets relative to the new interval: strictly before it, overlapping it, or strictly after it. We handle the buckets in order. First we pass along the intervals that end before the new start. Next we widen the new interval by pulling in the min start and max end of anything that overlaps. Finally we drop in the merged new interval and copy whatever remains.

Algorithm walkthrough

1Walk from the left, appending each interval whose end is smaller than the new interval's start.
2While the current interval's start is not past the new interval's end, expand the new interval's start down and end up to swallow it.
3Append the fully expanded new interval to the result.
4Append every remaining interval, all of which start after the new interval ends.
5Return the assembled result list.

Implementation

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        result = []
        i, n = 0, len(intervals)
        while i < n and intervals[i][1] < newInterval[0]:
            result.append(intervals[i])
            i += 1
        while i < n and intervals[i][0] <= newInterval[1]:
            newInterval[0] = min(newInterval[0], intervals[i][0])
            newInterval[1] = max(newInterval[1], intervals[i][1])
            i += 1
        result.append(newInterval)
        while i < n:
            result.append(intervals[i])
            i += 1
        return result

Time

O(n)

Space

O(n)

Each existing interval is examined at most once. No sorting is needed because the input is already ordered; the space is for the output list.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Arrays

After the pattern

Now solve one you haven't seen.

Slot a New Rehearsal Block is our own problem on the technique behind Insert Interval: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free