Insert Interval (LC 57)

Pattern: Linear Scan in 3 Phases (intervals are pre-sorted by start) Difficulty: Medium Key Concept: Split the existing intervals into three groups relative to newInterval: those that end before, those that overlap, and those that start after. Merge the overlapping group with newInterval.

Problem Statement

Given a list intervals of non-overlapping intervals sorted by start time, insert a new interval newInterval = [start, end] and return the resulting list, again sorted and non-overlapping (merge if needed).

Example

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

---

1. Algorithm & Pseudocode

result = []
i = 0, n = intervals.length

// Phase 1: intervals strictly before newInterval
while i < n and intervals[i].end < newInterval.start:
    result.add(intervals[i]); i++

// Phase 2: overlapping intervals — merge into newInterval
while i < n and intervals[i].start <= newInterval.end:
    newInterval.start = min(newInterval.start, intervals[i].start)
    newInterval.end   = max(newInterval.end,   intervals[i].end)
    i++
result.add(newInterval)

// Phase 3: intervals strictly after newInterval
while i < n:
    result.add(intervals[i]); i++

---

2. Step-by-Step Analysis

Why three phases Because the input is sorted by start, once an interval ends before newInterval.start it cannot overlap any future interval with newInterval. Symmetrically, an interval that starts after newInterval.end can never overlap. The “middle group” is exactly the contiguous run that overlaps.

The overlap test Two intervals [a1, b1] and [a2, b2] overlap iff a1 <= b2 && a2 <= b1. Since Phase 1 already advanced past everything with end < newInterval.start, the remaining overlap condition simplifies to intervals[i].start <= newInterval.end.

Why mutating newInterval is fine Each merge potentially widens both ends. After Phase 2, newInterval represents the union of itself and every overlapping original interval.

ASCII Trace for intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], new = [4,8]

Phase 1: keep [1,2]                 (2 < 4)
Phase 2: merge [3,5]  → new = [3,8]  (3 <= 8)
         merge [6,7]  → new = [3,8]
         merge [8,10] → new = [3,10] (8 <= 8)
Phase 3: append [12,16]              (12 > 10)

result = [[1,2], [3,10], [12,16]]

---

3. The Dry Run

Step	i	Current Interval	Phase	result after step	newInterval after step
1	0	[1,2]	1	[[1,2]]	[4,8]
2	1	[3,5]	2	[[1,2]]	[3,8]
3	2	[6,7]	2	[[1,2]]	[3,8]
4	3	[8,10]	2	[[1,2]]	[3,10]
5	4	[12,16]	3	[[1,2],[3,10],[12,16]]	[3,10]

---

4. Java Solution

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> result = new ArrayList<>();
        int i = 0, n = intervals.length;

        // Phase 1
        while (i < n && intervals[i][1] < newInterval[0]) {
            result.add(intervals[i]);
            i++;
        }

        // Phase 2
        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++;
        }
        result.add(newInterval);

        // Phase 3
        while (i < n) {
            result.add(intervals[i]);
            i++;
        }

        return result.toArray(new int[result.size()][]);
    }
}

Time: (O(n)) Space: (O(n)) for the output

---

5. The “Java vs. Others” Edge

• result.toArray(new int[result.size()][]) creates the jagged 2-D array directly — no Stream needed.
• Avoid sorting intervals again — the problem guarantees sorted input. Sorting would push complexity to (O(n \log n)).
• Mutating the input newInterval array is acceptable here; if the caller needs to keep it, clone first: newInterval = newInterval.clone();

---

6. Complexity Summary

Approach	Time	Space	Notes
Linear 3-phase	(O(n))	(O(n)) for output	Single pass over the sorted list.