Insert Interval

Practice Here

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

Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.

Note that you don't need to modify intervals in-place. You can make a new array and return it.

Brute Force: Linear Iteration#

• Intuition: Because the input intervals are already sorted, you can process them in three sequential phases: copy all intervals that end before the new interval starts, merge all intervals that overlap with the new interval, then copy the rest. No sorting or binary search is needed.
• Mechanics: The first loop advances past all intervals whose end is strictly before newInterval[0] — they are safe to copy as-is. The second loop merges every interval that overlaps with newInterval by expanding newInterval[0] and newInterval[1] greedily. The final loop appends the remaining non-overlapping intervals.
• Trade-off: O(n) time and O(n) space — as good as it gets for this problem since every interval must at least be read once. The simplicity of the three-phase scan makes this the most readable approach.

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

        vector<vector<int>> newIntervals;

        // before overlapping, when end_i < start_new
        while(i<n && intervals[i][1] < newInterval[0]){
            newIntervals.push_back(intervals[i]);
            i++;
        }

        while(i<n && newInterval[1] >= intervals[i][0])
        {
            newInterval[0] = min(newInterval[0], intervals[i][0]);
            newInterval[1] = max(newInterval[1], intervals[i][1]);
            i++;
        }
        newIntervals.push_back(newInterval);

        //after merging, add left intervals
        while(i<n){
            newIntervals.push_back(intervals[i]);
            i++;
        }
        return newIntervals;
    }
};

Time Complexity: O(n)

Space Complexity: O(n)

Better: Binary Search#

• Handle empty list:
  • If no intervals exist, return {newInterval}.
• Find first overlapping interval (startIdx):
  • Use binary search to find the first interval where end >= newInterval.start.
  • All intervals before this index are non-overlapping and go directly into the result.
• Find last overlapping interval (endIdx):
  • Use binary search to find the last interval where start <= newInterval.end.
  • All intervals after this index are non-overlapping and will be appended at the end.
• Add non-overlapping intervals before startIdx:
  • Push them to newIntervals.
• Merge all overlapping intervals:
  • Update newInterval.start = min(start) and newInterval.end = max(end) for all intervals from startIdx to endIdx.
• Push the merged newInterval into the result.
  • Add non-overlapping intervals after endIdx:
• Push them as they are to the result.

class Solution {
public:

    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        int n = intervals.size();
        if(n==0)
            return {newInterval};

        //Binary search for first overlapping interval
        int low = 0, high=n-1, startIdx=n;
        while(low<=high)
        {
            int mid = low + (high-low)/2;

            //end is not less than new start
            if(intervals[mid][1] >= newInterval[0]){
                startIdx = mid;
                high = mid-1;
            }else
                low = mid+1;
        }

        //Binary search for last overlapping interval
        low = 0, high=n-1;
        int endIdx=-1;
        while(low<=high)
        {
            int mid = low + (high-low)/2;

            //start is less than new end
            if(newInterval[1] >= intervals[mid][0]){
                endIdx = mid;
                low = mid+1;
            }else
                high = mid-1;
        }

        vector<vector<int>> newIntervals;

        for(int i=0;i<startIdx;i++){
            newIntervals.push_back(intervals[i]);
        }

        while(startIdx<=endIdx)
        {
            newInterval[0] = min(newInterval[0], intervals[startIdx][0]);
            newInterval[1] = max(newInterval[1], intervals[startIdx][1]);
            startIdx++;
        }
        newIntervals.push_back(newInterval);

        for(int i=endIdx+1; i<n;i++){
            newIntervals.push_back(intervals[i]);
        }
        return newIntervals;
    }
};

Time Complexity: O(n), Even though binary search has O(log n), the copying of intervals dominates

Space Complexity: O(n)

Alternate Approach: O(nlogn)#

• Intuition: Instead of carefully identifying the overlap boundaries, you can simply append newInterval to the list, re-sort, and then run a standard merge-intervals pass. The result is always correct because sorting establishes the invariant that overlapping intervals are adjacent.
• Mechanics: After appending and sorting, a single forward scan merges consecutive overlapping intervals in place using a write pointer idx. If the next interval's start is <= the current merged interval's end, extend the end; otherwise advance idx and record the next interval there.
• Trade-off: The sort makes this O(n log n), strictly worse than the O(n) linear approach. However it requires no special handling of the three phases, making it easy to reason about and re-use as a general merge-intervals routine.

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

        int idx = 0;
        for(int i=1;i<intervals.size();i++){
            if(intervals[i][0] <= intervals[idx][1]){
                intervals[idx][1] = max(intervals[idx][1], intervals[i][1]);
            }else{
                idx++;
                intervals[idx] = intervals[i];
            }
        }
        intervals.resize(idx+1);
        return intervals;
    }
};

In-Place: Binary Search + Erase/Insert#

• Intuition: Because the intervals are sorted, binary search can pinpoint exactly which interval first overlaps newInterval and which last overlaps it in O(log n). Everything between those two indices must be merged, and only the boundary values matter for the final merged interval's start and end.
• Mechanics: Two binary searches find startIdx (first interval with end >= newInterval[0]) and endIdx (last interval with start <= newInterval[1]). The merged interval inherits min(newInterval[0], intervals[startIdx][0]) and max(newInterval[1], intervals[endIdx][1]). The overlapping range is erased and replaced with the single merged interval using erase + insert.
• Trade-off: Binary search reduces the finding step to O(log n), but erase and insert on a vector shift elements — O(n) in the worst case. Net time is still O(n); the payoff is O(1) auxiliary space since no separate output array is built.

Use binary search to find the overlapping range in O(log n), then merge and splice in-place. Since intervals are sorted and non-overlapping, only the boundary intervals of the overlapping range matter for merging — startIdx has the minimum start, endIdx has the maximum end.

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

        // find first interval where end >= newInterval.start
        int low = 0, high = n - 1, startIdx = n;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (intervals[mid][1] >= newInterval[0]) {
                startIdx = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        // find last interval where start <= newInterval.end
        low = 0, high = n - 1;
        int endIdx = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (intervals[mid][0] <= newInterval[1]) {
                endIdx = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        // merge boundary intervals into newInterval before erasing
        if (startIdx <= endIdx) {
            newInterval[0] = min(newInterval[0], intervals[startIdx][0]);
            newInterval[1] = max(newInterval[1], intervals[endIdx][1]);
        }

        intervals.erase(intervals.begin() + startIdx, intervals.begin() + endIdx + 1);
        intervals.insert(intervals.begin() + startIdx, newInterval);

        return intervals;
    }
};

Time Complexity: O(n) — binary search is O(log n) but erase/insert shift up to n elements

Space Complexity: O(1) — modified in place, no auxiliary array