Insert Interval
Last Updated: April 4, 2026
Understanding the Problem
We have a sorted list of non-overlapping intervals, and we need to insert a new interval into it. The tricky part is that the new interval might overlap with one or more existing intervals, and when that happens, we need to merge them all into a single interval.
Think of it like a timeline. You have blocks of time already reserved (the existing intervals), and you're adding a new block. If your new block overlaps with existing reservations, they all merge into one larger block. If it doesn't overlap with anything, it just slots into the right position.
The key observation is that because the intervals are already sorted, we can split the problem into three phases: intervals that come entirely before the new interval, intervals that overlap with it, and intervals that come entirely after it. The first and last groups stay unchanged. The middle group gets merged with the new interval.
Key Constraints:
0 <= intervals.length <= 10^4→ With n up to 10,000, O(n log n) and O(n) solutions both work comfortably. O(n^2) would be borderline.intervals is sorted by start_i→ Already sorted. We can process them in a single left-to-right pass without needing to sort.0 <= start_i <= end_i <= 10^5→ No negative values, and start is always less than or equal to end. No invalid intervals.intervalshas no overlapping intervals → The existing list is clean. Any overlap must involve the new interval.
Approach 1: Brute Force (Insert and Re-merge)
Intuition
The simplest approach: just add the new interval to the list, sort everything by start time, and then merge any overlapping intervals. This is the same logic as the "Merge Intervals" problem (LeetCode #56), with an extra insertion step at the beginning.
It's not the most efficient approach since we're sorting an already-sorted list, but it's correct and easy to reason about.
Algorithm
- Add
newIntervalto theintervalslist. - Sort the entire list by start time.
- Initialize a result list with the first interval.
- For each subsequent interval, check if it overlaps with the last interval in the result (i.e., its start is less than or equal to the last interval's end).
- If it overlaps, merge by updating the end of the last result interval to
max(lastEnd, currentEnd). - If it doesn't overlap, add it to the result as a new interval.
- Return the result.
Example Walkthrough
Code
- Time Complexity: O(n log n). Sorting dominates. The merge pass is O(n), but the sort brings us to O(n log n). We're sorting an already-sorted list plus one extra element, which is wasteful.
- Space Complexity: O(n). We create a new list to hold all intervals plus the result.
Since the intervals are already sorted, we're paying O(n log n) for a sort that shouldn't be necessary. Can we find the right position for the new interval and handle merges in a single left-to-right pass?
Approach 2: Linear Scan with Merge
Intuition
Here's the key insight: because the intervals are already sorted by start time, we can split the problem into three clean phases.
Phase 1: All intervals that end before the new interval starts. These don't overlap with the new interval at all, so we add them directly to the result.
Phase 2: All intervals that overlap with the new interval. As we find overlapping intervals, we merge them into the new interval by expanding its boundaries: take the minimum start and maximum end.
Phase 3: All intervals that start after the new interval ends. These come after, so we add them directly to the result.
Each interval is examined exactly once, and we don't need to sort anything.
The three-phase approach exploits the sorted order of the input. Since intervals are sorted by start time and don't overlap with each other, there's a clear boundary: once we find the first interval that could overlap with the new interval, all subsequent overlapping intervals are contiguous. There can't be a gap in the middle where some interval doesn't overlap but a later one does.
Algorithm
- Initialize an empty result list and an index
i = 0. - Phase 1 (Before): While
i < nandintervals[i][1] < newInterval[0], addintervals[i]to the result and incrementi. These intervals end before the new interval starts. - Phase 2 (Merge): While
i < nandintervals[i][0] <= newInterval[1], merge: setnewInterval[0] = min(newInterval[0], intervals[i][0])andnewInterval[1] = max(newInterval[1], intervals[i][1]). Incrementi. - Add the (possibly merged)
newIntervalto the result. - Phase 3 (After): While
i < n, add the remainingintervals[i]to the result and incrementi. - Return the result.
Example Walkthrough
Code
- Time Complexity: O(n). We scan through all intervals exactly once. Each interval is processed in one of the three phases, and each phase does O(1) work per interval.
- Space Complexity: O(n). The result list holds up to n + 1 intervals. If we don't count the output, the extra space is O(1).