Merge Intervals — Insert Interval

↗ LeetCode: Insert Interval · Medium · pattern chapter →

Asked atMetaAmazonGoogleLinkedIn

Given sorted, non-overlapping intervals and a newInterval, insert it and merge if needed.

Example 1 — intervals=[[1,3],[6,9]], newInterval=[2,5] → [[1,5],[6,9]]Example 2 — intervals=[[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval=[4,8] → [[1,2],[3,10],[12,16]]Example 3 — intervals=[], newInterval=[5,7] → [[5,7]]

Constraints — 0 ≤ intervals.length ≤ 10⁴. Brute concat + merge is O(n log n) = ~10⁵ ops at n=10⁴, ~10⁶ ops under 10 queries/sec load. Single sorted pass with three phases (before / overlap / after) is O(n) = 10⁴ ops — 10× faster on the hot path.

Progressive Hints

Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.

---

⏱️Interview timer00:00

Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.

Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.

Approach 1 — Append + full merge

Insert then run Merge Intervals O(n log n).

Approach 2 — Single-pass three-phase (canonical)

Insight. Since intervals are pre-sorted, walk once:

1. Copy intervals ending before newInterval starts.
2. Merge all intervals overlapping newInterval.
3. Copy intervals starting after newInterval ends.

int[][] insert(int[][] intervals, int[] newInterval) {
    List<int[]> out = new ArrayList<>();
    int i = 0, n = intervals.length;
    while (i < n && intervals[i][1] < newInterval[0]) out.add(intervals[i++]);
    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++;
    }
    out.add(newInterval);
    while (i < n) out.add(intervals[i++]);
    return out.toArray(new int[0][]);
}

Execution Trace

3-phase — intervals=[[1,2],[3,5],[6,7],[8,10],[12,16]], new=[4,8]

Step 1 / 4[1,2] ends before 4

Complexity — Time O(n); Space O(n).

---

Try it yourself

Complexity summary

Approach	Time	Space	Grade
Append + merge	O(n log n)	O(n)	baseline
Three-phase single pass	O(n)	O(n)	canonical

When to use which

• Streaming inserts into sorted list → repeated three-phase.
• Batch merges → sort once, then O(n) merge.
• Return "would this overlap?" boolean → binary-search for first end ≥ new.start.

✨AI Study CompanionBeta

Related problems

• Merge Intervals
• Interval List Intersections
• Remove Covered Intervals

Was this page helpful?

📚 Related problems

• → Remove Covered Intervals
• → My Calendar II
• → Meeting Rooms II