Insert Interval

Difficulty: Medium
Topics: Array
Link: https://leetcode.com/problems/insert-interval/

Problem Description

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.

Example 1:


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

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: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

Constraints:

0 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 105
intervals is sorted by starti in ascending order.
newInterval.length == 2
0 <= start <= end <= 105

Solution

1. Problem Deconstruction

Technical Restatement

Given a sorted array intervals of non-overlapping closed intervals where intervals[i] = [start_i, end_i] and start_i ≤ end_i, and a newInterval = [start, end], insert newInterval into intervals while preserving:

Sorted Order: The result must remain sorted by ascending start_i.
Non-Overlapping: Merge any overlapping intervals into consolidated intervals.
Return a new array (no in-place modification required).

Beginner-Friendly Explanation

Imagine you have a list of time periods (like meetings) that don’t overlap and are sorted by start time. You need to add a new time period to this list. If the new period overlaps with any existing ones, combine them into a single continuous period. Keep the final list sorted and free of overlaps.

Example:

Original meetings: [[1,3], [6,9]]
New meeting: [2,5] (overlaps with [1,3])
Result: [[1,5], [6,9]] (combined [1,3] and [2,5] into [1,5]).

Mathematical Formulation

Let $I = \{[a_i, b_i]\}_{i=1}^n$ be a set of intervals where $a_i \leq b_i$ and $a_i \leq a_{i+1}$ (sorted), and $[a_{\text{new}}, b_{\text{new}}]$ be the new interval. The goal is to compute:

I' = \left\{ \left[ \min(c_j), \max(d_j) \right] \mid \text{for all maximally merged contiguous intervals} \right\}

where $\bigcup [c_j, d_j] = \bigcup I \cup [a_{\text{new}}, b_{\text{new}}]$ and $[c_j, d_j]$ are disjoint.

Constraint Analysis

0 ≤ intervals.length ≤ 10^4:
- Empty input → return [newInterval].
- Large input → requires $O(n)$ or $O(n \log n)$ algorithm.
0 ≤ start_i ≤ end_i ≤ 10^5:
- Intervals are non-negative; handle cases where newInterval starts before/after all existing intervals.
Sorted Order:
- Leverage binary properties; no need for explicit sorting after insertion.
Non-Overlapping Input:
- Merging only occurs between newInterval and existing intervals, never between existing intervals alone.

2. Intuition Scaffolding

Real-World Metaphor

Like merging train schedules: You have a timetable of non-overlapping train departures (intervals). Adding a new train (newInterval) might extend existing slots if arrival/departure times overlap. The station master combines overlapping slots into continuous blocks.

Gaming Analogy

In a strategy game, each interval is a troop deployment phase. Inserting a new deployment phase requires merging overlapping phases (e.g., archers deployed from [4,8] merging with infantry at [3,5] and cavalry at [6,10] → consolidated deployment [3,10]).

Mathematical Analogy

Finding the connected components in a 1D number line where nodes are intervals. Inserting newInterval creates new edges (overlaps), requiring recomputation of the component’s min/max bounds.

Common Pitfalls

Ignoring Partial Overlaps:
- [1,5] and [3,7] → should merge to [1,7], not [1,5] + [3,7].
Edge-Overlap Miss:
- [1,5] and [5,10] should merge to [1,10] (edge-touching intervals).
Incorrect Insertion Position:
- Inserting [2,3] into [[1,4],[5,6]] must merge with [1,4], not create a new entry.
Unmerged Disjoint Intervals:
- Failing to merge multiple intervals (e.g., newInterval = [4,8] merging [3,5], [6,7], [8,10]).
Boundary Blindness:
- newInterval = [0,0] should not merge with [1,2] since 0 < 1.

3. Approach Encyclopedia

Brute Force

Append newInterval to intervals.
Sort by start_i ( $O(n \log n)$ ).
Traverse and merge overlaps: if curr.end >= next.start, merge to [curr.start, max(curr.end, next.end)].

Pseudocode:

def insert(intervals, newInterval):
    intervals.append(newInterval)
    intervals.sort(key=lambda x: x[0])  # O(n log n)
    merged = []
    for interval in intervals:
        if not merged or merged[-1][1] < interval[0]:
            merged.append(interval)
        else:
            merged[-1][1] = max(merged[-1][1], interval[1])
    return merged

Complexity: Time $O(n \log n)$ (sorting dominates), Space $O(n)$ .

Visualization:

Original: [[1,2], [3,5], [6,7], [8,10], [12,16]] + [4,8]
Append:  [[1,2], [3,5], [6,7], [8,10], [12,16], [4,8]]
Sort:    [[1,2], [3,5], [4,8], [6,7], [8,10], [12,16]]
Merge:   [[1,2]] → [[1,2],[3,5]] → merge [3,5] & [4,8] → [3,8] 
          → merge [3,8] & [6,7] → [3,8] → merge [3,8] & [8,10] → [3,10] → add [12,16]
Output:  [[1,2], [3,10], [12,16]]

Optimal Approach (Linear Scan)

Phase 1: Add intervals ending before newInterval starts (no overlap).
Phase 2: Merge all intervals overlapping with newInterval by updating newInterval = [min(start), max(end)].
Phase 3: Add remaining intervals.