Insert Interval

Problem Description

You are given an array of non-overlapping intervals intervals where intervals[i] = [start, end] represents the start and the end of the ith interval, sorted in ascending order by start. You are also given a new interval newInterval = [start, end] that represents another interval to insert.

Insert newInterval into intervals such that the list is still sorted in ascending order by start and still contains no overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.

Examples

Constraints

• 0 ≤ intervals.length ≤ 10⁴
• intervals[i].length == 2
• 0 ≤ start ≤ end ≤ 10⁵
• intervals is sorted by start in ascending order.
• newInterval.length == 2
• 0 ≤ newInterval[0] ≤ newInterval[1] ≤ 10⁵

Adding Left, Merging Overlaps, and Appending Right

To insert the new interval and maintain sorting without overlaps, we can process the input list in three distinct stages:

1. Left Portion: Add all intervals that end before newInterval starts (no overlap).
2. Overlap Portion: For all intervals that overlap with newInterval (meaning their start is less than or equal to newInterval[1]), merge them into newInterval by taking newInterval[0] = min(newInterval[0], current[0]) and newInterval[1] = max(newInterval[1], current[1]). Once no more overlaps occur, add the merged newInterval.
3. Right Portion: Add all remaining intervals that start after newInterval ends (no overlap).

This linear split processes each interval exactly once, running in O(n) time.

Solution 1: Three-Stage Linear Sweep

Iterate through the sorted intervals list using a loop index to handle the three portions.

import java.util.ArrayList;
import java.util.List;

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

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

        // Stage 2: merge all overlapping intervals
        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); // add the merged interval

        // Stage 3: add all remaining intervals
        while (i < n) {
            result.add(intervals[i]);
            i++;
        }

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

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

        # Stage 1: add all intervals that end before the new interval starts
        while i < n and intervals[i][1] < newInterval[0]:
            result.append(intervals[i])
            i += 1

        # Stage 2: merge all overlapping intervals
        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)  # add the merged interval

        # Stage 3: add all remaining intervals
        while i < n:
            result.append(intervals[i])
            i += 1

        return result

#include <vector>
#include <algorithm>

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

        // Stage 1: add all intervals that end before the new interval starts
        while (i < n && intervals[i][1] < newInterval[0]) {
            result.push_back(intervals[i]);
            i++;
        }

        // Stage 2: merge all overlapping intervals
        while (i < n && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = std::min(newInterval[0], intervals[i][0]);
            newInterval[1] = std::max(newInterval[1], intervals[i][1]);
            i++;
        }
        result.push_back(newInterval); // add the merged interval

        // Stage 3: add all remaining intervals
        while (i < n) {
            result.push_back(intervals[i]);
            i++;
        }

        return result;
    }
};

Complexity Analysis:

• Time Complexity: O(n) where n is the number of intervals. We visit each interval once.
• Space Complexity: O(1) auxiliary space (excluding the output array).

Where it breaks: Nothing breaks for standard sorted inputs. If the input list is not sorted by start coordinates, the three-stage assumption fails, and you must sort the intervals array first, increasing complexity to O(n log n).

Common Mistakes

• Incorrect condition for overlap. An interval overlaps with newInterval if intervals[i][0] <= newInterval[1] and intervals[i][1] >= newInterval[0]. In our sequential sweep, the first loop already filters out intervals where intervals[i][1] < newInterval[0], so checking intervals[i][0] <= newInterval[1] in stage 2 is sufficient.
• Modifying elements without merging. Simply inserting the new interval without combining borders results in overlapping intervals in the output.
• Off-by-one errors on index termination. Ensure you use index bounds checks i < n on all three loops to prevent segmentation faults.

Frequently Asked Questions

Can we solve this using binary search? Yes. You can use binary search to locate the insertion indices for newInterval[0] and newInterval[1]. However, merging overlapping intervals and slicing the array still takes O(n) time in the worst case due to element shifts, so the time complexity remains O(n).

What if the input intervals list is empty? If intervals is empty, the first loop does not run, the merge loop does not run, and the code appends newInterval to the empty list and returns it, which is correct.

What does this problem test in interviews? It tests your ability to parse structured range lists, manage multiple index pointers, and consolidate overlapping intervals in-place.

← All Problems