Skip to main content
CodePeetCodePeet
CodePeet 250

Insert Interval

MEDIUMProblemSolveExternal Links

Description

You are given a list of non-overlapping intervals that are already sorted in ascending order by their start values. Each interval is a pair [start, end]. You are also given a single new interval [start, end] that you need to insert into the list.

After inserting the new interval, the resulting list must still be sorted by start values and must not contain any overlapping intervals. If the new interval overlaps with one or more existing intervals, you need to merge all of them into a single combined interval.

Return the updated list of intervals after the insertion and any necessary merging.

You do not need to modify the original list in place — creating and returning a new list is acceptable.

Examples

Example 1

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

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

Explanation: The new interval [2, 5] overlaps with the existing interval [1, 3] because 2 falls within the range [1, 3]. They merge to form [1, 5] — taking the minimum start (1) and maximum end (5). The interval [6, 9] does not overlap with [1, 5] since 6 > 5, so it remains unchanged.

Example 2

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

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

Explanation: The new interval [4, 8] overlaps with [3, 5] (since 4 falls within [3, 5]), with [6, 7] (since 6 ≤ 8), and with [8, 10] (since 8 ≤ 8). All four intervals — [3, 5], [4, 8], [6, 7], [8, 10] — are merged into a single interval [3, 10]. The intervals [1, 2] and [12, 16] do not overlap with anything, so they remain intact.

Example 3

Input: intervals = [], newInterval = [5, 7]

Output: [[5, 7]]

Explanation: The list is empty, so we simply return the new interval as the only entry. No merging is needed.

Constraints

  • 0 ≤ intervals.length ≤ 10^4
  • intervals[i].length == 2
  • 0 ≤ start_i ≤ end_i ≤ 10^5
  • intervals is sorted by start_i in ascending order
  • newInterval.length == 2
  • 0 ≤ start ≤ end ≤ 10^5

Editorial

Brute Force

Intuition

The simplest way to think about this problem is to forget about the special structure of the input (sorted, non-overlapping) and just treat it as a general merge-intervals problem.

We can add the new interval to the existing list, re-sort everything by start time, and then merge all overlapping intervals using the standard merge-intervals algorithm.

Think of it like having a sorted row of books on a shelf with gaps between groups. Someone hands you a new book. Instead of carefully figuring out where it goes and which groups it bridges, you just toss it in the pile, re-sort everything, and then re-organize from scratch.

This approach is correct and easy to understand, but it throws away the valuable information that the input is already sorted — making it do more work than necessary.

Step-by-Step Explanation

Let's trace through with intervals = [[1, 3], [6, 9]], newInterval = [2, 5]:

Step 1: Add newInterval to the list. Combined = [[1, 3], [6, 9], [2, 5]].

Step 2: Sort by start value. Sorted = [[1, 3], [2, 5], [6, 9]].

Step 3: Initialize result with the first interval. Result = [[1, 3]].

Step 4: Process [2, 5]. Compare start=2 with last result's end=3. Is 2 ≤ 3? YES — overlap detected.

Step 5: Merge: update last result's end to max(3, 5) = 5. Result = [[1, 5]].

Step 6: Process [6, 9]. Compare start=6 with last result's end=5. Is 6 ≤ 5? NO — no overlap.

Step 7: Add [6, 9] as a new entry. Result = [[1, 5], [6, 9]].

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

Brute Force — Insert, Sort, and Merge — Watch how we add the new interval to the list, re-sort everything, and then use the standard merge-intervals algorithm to produce the final result.

Algorithm

  1. Add the new interval to the existing list of intervals
  2. Sort the combined list by start values
  3. Initialize a result list with the first interval
  4. For each remaining interval:
    • If it overlaps with the last interval in the result (start ≤ last end), merge them by extending the last interval's end
    • Otherwise, add it as a new entry in the result
  5. Return the result list

Code

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        intervals.push_back(newInterval);
        sort(intervals.begin(), intervals.end());

        vector<vector<int>> result;
        result.push_back(intervals[0]);

        for (int i = 1; i < intervals.size(); i++) {
            vector<int>& last = result.back();
            if (intervals[i][0] <= last[1]) {
                last[1] = max(last[1], intervals[i][1]);
            } else {
                result.push_back(intervals[i]);
            }
        }

        return result;
    }
};
class Solution:
    def insert(self, intervals: list[list[int]], newInterval: list[int]) -> list[list[int]]:
        intervals.append(newInterval)
        intervals.sort()

        result = [intervals[0]]

        for i in range(1, len(intervals)):
            last = result[-1]
            if intervals[i][0] <= last[1]:
                last[1] = max(last[1], intervals[i][1])
            else:
                result.append(intervals[i])

        return result
import java.util.*;

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int[][] combined = new int[intervals.length + 1][2];
        for (int i = 0; i < intervals.length; i++) {
            combined[i] = intervals[i];
        }
        combined[intervals.length] = newInterval;
        Arrays.sort(combined, (a, b) -> a[0] - b[0]);

        List<int[]> result = new ArrayList<>();
        result.add(combined[0]);

        for (int i = 1; i < combined.length; i++) {
            int[] last = result.get(result.size() - 1);
            if (combined[i][0] <= last[1]) {
                last[1] = Math.max(last[1], combined[i][1]);
            } else {
                result.add(combined[i]);
            }
        }

        return result.toArray(new int[result.size()][]);
    }
}

Complexity Analysis

Time Complexity: O(n log n)

Adding the new interval is O(1). Sorting the combined list of n+1 intervals takes O(n log n). The merge pass is O(n). The dominant term is the sorting step: O(n log n).

Space Complexity: O(n)

The result list can hold up to n+1 intervals. The sort may use O(log n) auxiliary space. Overall: O(n).

Why This Approach Is Not Efficient

The brute force approach re-sorts the entire list even though the input is already sorted. Sorting takes O(n log n), but since we are only adding one interval to an already-sorted list, we should be able to do much better.

The critical waste is in the sort step. The input intervals are already in ascending order by start time. The only disruption is the single new interval. We can take advantage of this structure by processing the intervals in a single left-to-right scan:

  1. First, collect all intervals that end before the new interval starts (no overlap possible)
  2. Then, merge all intervals that overlap with the new interval
  3. Finally, collect all intervals that start after the new interval ends (no overlap possible)

This three-phase approach processes each interval exactly once in O(n) time, eliminating the unnecessary O(n log n) sort entirely.

Optimal Approach - Linear Scan with Three Phases

Intuition

Since the input intervals are already sorted and non-overlapping, inserting a new interval creates at most three zones when you scan left to right:

Zone 1 — Before: Intervals that end entirely before the new interval starts. These cannot possibly overlap with the new interval, so they go directly into the result unchanged.

Zone 2 — Overlap: Intervals that overlap with the new interval. Two intervals overlap if one starts before the other ends. As we encounter each overlapping interval, we absorb it into the new interval by expanding the new interval's start to the minimum and its end to the maximum. After processing all overlapping intervals, we add the fully-merged new interval to the result.

Zone 3 — After: Intervals that start entirely after the new interval ends. Like Zone 1, these have no overlap, so they go directly into the result.

Imagine a timeline with colored blocks already placed neatly with gaps between them. You slide a new block in from above. Some existing blocks are entirely to the left of it, some touch or overlap it, and some are entirely to the right. You pick up all the overlapping blocks, merge them with the new one into a single larger block, and place everything back on the timeline.

Step-by-Step Explanation

Let's trace through with intervals = [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], newInterval = [4, 8]:

Phase 1 — Collect non-overlapping intervals before newInterval:

Step 1: Check [1, 2]: does it end before newInterval starts? Is 2 < 4? YES — [1, 2] is entirely before [4, 8]. Add [1, 2] to result.

Step 2: Check [3, 5]: does it end before newInterval starts? Is 5 < 4? NO — [3, 5] might overlap with [4, 8]. Stop Phase 1.

Phase 2 — Merge overlapping intervals with newInterval:

Step 3: Check [3, 5]: does it start before or at newInterval's end? Is 3 ≤ 8? YES — overlap. Merge: newInterval becomes [min(4, 3), max(8, 5)] = [3, 8].

Step 4: Check [6, 7]: does it start before or at newInterval's end? Is 6 ≤ 8? YES — overlap. Merge: newInterval becomes [min(3, 6), max(8, 7)] = [3, 8] (no change this time).

Step 5: Check [8, 10]: does it start before or at newInterval's end? Is 8 ≤ 8? YES — overlap. Merge: newInterval becomes [min(3, 8), max(8, 10)] = [3, 10].

Step 6: Check [12, 16]: does it start before or at newInterval's end? Is 12 ≤ 10? NO — no overlap. Stop Phase 2. Add merged newInterval [3, 10] to result.

Phase 3 — Collect remaining intervals:

Step 7: Add [12, 16] to result.

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

Optimal — Three-Phase Linear Scan — Watch the three-phase linear scan: first collect intervals before the new one, then merge all overlapping intervals into it, and finally collect intervals after it.

Algorithm

  1. Initialize an empty result list and a pointer i = 0
  2. Phase 1 (Before): While i < n and intervals[i] ends before newInterval starts (intervals[i][1] < newInterval[0]):
    • Add intervals[i] to the result
    • Increment i
  3. Phase 2 (Overlap): While i < n and intervals[i] starts before or at newInterval's end (intervals[i][0] ≤ newInterval[1]):
    • Merge: newInterval[0] = min(newInterval[0], intervals[i][0])
    • Merge: newInterval[1] = max(newInterval[1], intervals[i][1])
    • Increment i
  4. Add the merged newInterval to the result
  5. Phase 3 (After): While i < n:
    • Add intervals[i] to the result
    • Increment i
  6. Return the result

Code

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> result;
        int i = 0;
        int n = intervals.size();

        // Phase 1: Add all intervals that end before newInterval starts
        while (i < n && intervals[i][1] < newInterval[0]) {
            result.push_back(intervals[i]);
            i++;
        }

        // Phase 2: Merge all overlapping intervals with newInterval
        while (i < n && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = min(newInterval[0], intervals[i][0]);
            newInterval[1] = max(newInterval[1], intervals[i][1]);
            i++;
        }
        result.push_back(newInterval);

        // Phase 3: Add all intervals that start after newInterval ends
        while (i < n) {
            result.push_back(intervals[i]);
            i++;
        }

        return result;
    }
};
class Solution:
    def insert(self, intervals: list[list[int]], newInterval: list[int]) -> list[list[int]]:
        result = []
        i = 0
        n = len(intervals)

        # Phase 1: Add all intervals that end before newInterval starts
        while i < n and intervals[i][1] < newInterval[0]:
            result.append(intervals[i])
            i += 1

        # Phase 2: Merge all overlapping intervals with newInterval
        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)

        # Phase 3: Add all intervals that start after newInterval ends
        while i < n:
            result.append(intervals[i])
            i += 1

        return result
import java.util.*;

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> result = new ArrayList<>();
        int i = 0;
        int n = intervals.length;

        // Phase 1: Add all intervals that end before newInterval starts
        while (i < n && intervals[i][1] < newInterval[0]) {
            result.add(intervals[i]);
            i++;
        }

        // Phase 2: Merge all overlapping intervals with newInterval
        while (i < n && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
            newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
            i++;
        }
        result.add(newInterval);

        // Phase 3: Add all intervals that start after newInterval ends
        while (i < n) {
            result.add(intervals[i]);
            i++;
        }

        return result.toArray(new int[result.size()][]);
    }
}

Complexity Analysis

Time Complexity: O(n)

We traverse the intervals list exactly once. Each interval is visited once across the three while-loops (the pointer i only moves forward). Every operation inside each loop body — comparisons, min/max, and appending — is O(1). So the total time is O(n).

This is a significant improvement over the brute force O(n log n) because we leverage the fact that the input is already sorted, eliminating the need to re-sort.

Space Complexity: O(n)

The result list can hold up to n + 1 intervals (all original intervals plus the new one, if no merges occur). No other data structures grow with input size. So overall space is O(n).

This is optimal — we must examine every interval at least once to determine if it overlaps with the new interval, so O(n) is the lower bound for time. And we must store the result, so O(n) is the lower bound for space.