Insert Interval

How it works

We are inserting newInterval into a list of sorted, non-overlapping intervals and want the final result to remain sorted and non-overlapping.

A greedy approach works because as we scan from left to right, every interval falls into one of three cases relative to newInterval:

1. Completely after newInterval

   • If newInterval ends before the current interval starts, there will be no overlap with any later interval either.
   • So we can safely place newInterval here and return the answer immediately.

2. Completely before newInterval

   • If the current interval ends before newInterval starts, it can be added to the result unchanged.

3. Overlapping with newInterval

   • If they overlap, we merge them by expanding newInterval to cover both ranges.

By continuously merging when needed and stopping early when newInterval is placed, we solve it in one pass.

Steps

1. Initialize an empty list res.
2. Iterate through each interval in intervals:
3. If newInterval ends before the current interval starts:
   • Append newInterval to res
   • Return res plus the remaining intervals (since everything after is already sorted and non-overlapping)
4. Else if newInterval starts after the current interval ends:
   • Append the current interval to res (it is safely before newInterval)
5. Else (they overlap):
   • Merge by updating newInterval:
     • newInterval.start = min(newInterval.start, interval.start)
     • newInterval.end = max(newInterval.end, interval.end)
6. If the loop ends, it means newInterval belongs at the end:
   • Append newInterval to res
7. Return res

Complexity

• Time complexity: O(n)
• Space complexity:
  • O(1) extra space.
  • O(n) space for the output list.

Things to watch for

Incorrect Overlap Detection

Using the wrong condition to detect overlapping intervals leads to incorrect merging. Two intervals [a, b] and [c, d] overlap when a <= d AND c <= b. A common mistake is checking only one direction or using strict inequality (< instead of <=), which fails for adjacent intervals like [1, 2] and [2, 3] that should merge.

Forgetting to Add the New Interval at the End

When the new interval belongs after all existing intervals (its start is greater than all existing ends), the merging loop never triggers and the new interval is never added. The algorithm must append the new interval to the result after the loop completes if it was not already inserted.

Mutating the Original Input Array

Some solutions modify the newInterval array during merging, which can cause issues if the caller expects the original input to remain unchanged. In languages where arrays are passed by reference, this side effect may lead to unexpected behavior in the calling code.

from typing import List

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        res = []

        for i in range(len(intervals)):
            if newInterval[1] < intervals[i][0]:
                res.append(newInterval)
                return res + intervals[i:]
            elif newInterval[0] > intervals[i][1]:
                res.append(intervals[i])
            else:
                newInterval = [
                    min(newInterval[0], intervals[i][0]),
                    max(newInterval[1], intervals[i][1]),
                ]
        res.append(newInterval)
        return res

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> res;
        int newStart = newInterval[0];
        int newEnd = newInterval[1];
        int n = intervals.size();
        for (int i = 0; i < n; i++) {
            if (intervals[i][0] > newEnd) {
                res.push_back(newInterval);
                copy(intervals.begin() + i, intervals.end(), back_inserter(res));
                return res;
            } else if (intervals[i][1] < newStart) {
                res.push_back(intervals[i]);
            } else {
                newInterval[0] = min(newInterval[0], intervals[i][0]);
                newInterval[1] = max(newInterval[1], intervals[i][1]);
            }
        }
        res.push_back(newInterval);
        return res;
    }
};