Insert Interval (LC 57)

Pattern: Merge Intervals
Difficulty: Medium
Key Concept: Insert a new interval into a sorted, non-overlapping list by scanning in three phases—before, merge, after—without full resorting.

Problem Statement

You are given an array of intervals where intervals[i] = [start_i, end_i] are sorted by start time and do not overlap. You are also given newInterval = [start, end].

Insert newInterval into intervals such that the result is still sorted and non-overlapping, merging newInterval with any existing intervals that overlap it.

Input: intervals — int[][] sorted, disjoint; newInterval — int[] of length 2.
Output: int[][] — merged, sorted, non-overlapping intervals covering the union of all intervals plus newInterval.

---

1. Algorithm & Pseudocode

Brute force

1. Copy all intervals plus newInterval into a list.
2. Sort the list by start time (e.g. Arrays.sort on a 2D array or sort a list of int[]).
3. Merge adjacent overlapping intervals in one linear scan (same idea as LC 56).

Optimal (three-phase linear scan)

1. Let newStart = newInterval[0], newEnd = newInterval[1], i = 0, n = intervals.length, result empty.
2. Phase A — strictly before: While i < n and intervals[i][1] < newStart, append intervals[i] to result, i++.
3. Phase B — merge: While i < n and intervals[i][0] <= newEnd, set newStart = min(newStart, intervals[i][0]), newEnd = max(newEnd, intervals[i][1]), i++. Append [newStart, newEnd] once.
4. Phase C — strictly after: While i < n, append intervals[i], i++.
5. Convert result to int[][] (e.g. result.toArray(new int[0][])).

---

2. Step-by-Step Analysis (Beginner-Friendly)

• Why not only sort? Sorting works but costs O(n log n). The input is already sorted except for one new interval; we can exploit order with a single O(n) pass.
• Phase A: Any interval that ends before newStart cannot overlap the new interval, so we copy it unchanged.
• Phase B: If an interval’s start is ≤ the current merged end, it overlaps the growing block; we expand newStart/newEnd to the union. We stop when the next interval starts after newEnd.
• Phase C: Everything left starts after the merged block, so no further merging with the inserted interval—append as-is.
• Why intervals[i][0] <= newEnd? Overlap (touching counts as mergeable in this problem) means the next interval is not entirely to the right of the merged region.

---

3. The Dry Run

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
So initially newStart = 2, newEnd = 5, i = 0, result = [].

Step	Phase	i	Action	newStart	newEnd	result (after step)
1	A	0	[1,3]: 3 < 2? No — skip A for this interval	2	5	[]
2	B	0	[1,3]: 1 <= 5? Yes — merge: newStart = min(2,1)=1, newEnd = max(5,3)=5, i → 1	1	5	[]
3	B	1	[6,9]: 6 <= 5? No — exit B	1	5	[]
4	B	—	Append merged [1,5]	1	5	[[1,5]]
5	C	1	Append [6,9], i → 2	1	5	[[1,5],[6,9]]
6	—	2	i == n, done	—	—	[[1,5],[6,9]]

Output: [[1,5],[6,9]].

---

4. Java Solution

Brute Force

import java.util.*;

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> list = new ArrayList<>();
        for (int[] iv : intervals) {
            list.add(iv);
        }
        list.add(newInterval);

        list.sort(Comparator.comparingInt(a -> a[0]));

        List<int[]> merged = new ArrayList<>();
        for (int[] cur : list) {
            if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < cur[0]) {
                merged.add(cur);
            } else {
                int[] last = merged.get(merged.size() - 1);
                last[1] = Math.max(last[1], cur[1]);
            }
        }
        return merged.toArray(new int[0][]);
    }
}

Time: O(n log n) (sort dominates). Space: O(n) for the list and merge buffer.

Optimal

import java.util.*;

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

        while (i < n && intervals[i][1] < newStart) {
            res.add(intervals[i]);
            i++;
        }
        while (i < n && intervals[i][0] <= newEnd) {
            newStart = Math.min(newStart, intervals[i][0]);
            newEnd = Math.max(newEnd, intervals[i][1]);
            i++;
        }
        res.add(new int[] { newStart, newEnd });
        while (i < n) {
            res.add(intervals[i]);
            i++;
        }
        return res.toArray(new int[0][]);
    }
}

Time: O(n). Space: O(n) for the output list (excluding output, only O(1) extra).

---

5. The “Java vs. Others” Edge

• List.toArray(new int[0][]): Converts ArrayList<int[]> to int[][]. The new int[0][] trick lets the JVM allocate an array of the correct runtime size; sizing manually is error-prone.
• Integer.compare(a, b) (or Comparator.comparingInt(a -> a[0])): Avoids overflow pitfalls of a - b when values are near Integer.MIN_VALUE/MAX_VALUE.
• ArrayList growth: Backed by an array; when full, capacity grows (typically about 1.5×), so amortized append is O(1)—good to mention in interviews when discussing space spikes during building.
• C++/Python contrast: C++ might use vector<vector<int>> and push_back; Python lists are dynamic but returning list[list[int]] vs LeetCode’s List[List[int]] is similar. Java’s explicit int[][] + ArrayList<int[]> split is a common LeetCode pattern.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	O(n log n)	O(n)	Sort all, then merge like LC 56.
Optimal	O(n)	O(n) output, O(1) auxiliary	Single pass using sorted input + three phases.