Difficulty: MediumIntervals

Insert Interval

Problem in Plain English

You are given a sorted list of non-overlapping intervals plus one new interval to insert. Splice it into the right position, merging every interval it overlaps, and return the still-sorted non-overlapping result.

Problem Statement

Given a sorted list of non-overlapping closed intervals intervals and one closed interval newInterval, insert the newcomer and merge every overlap. Return intervals sorted by start with no overlaps. Closed means both endpoints belong to the interval: sharing even one endpoint counts as overlap.

The input list may be empty and an interval may be a single point. The implementations below preserve both arguments and return newly owned interval rows, so changing the result later does not change either input.

Constraints

$0 \leq n = \mathrm{intervals.length} \leq 10^4$ .
Every existing row and newInterval contain exactly two endpoints.
$0 \leq \mathrm{start} \leq \mathrm{end} \leq 10^5$ for every interval, including the newcomer.
Existing intervals are sorted by start and do not overlap; each existing end is strictly smaller than the following start.

Examples

Example 1

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

The newcomer overlaps [1,3], producing [1,5]. The strict gap between 5 and 6 keeps [6,9] separate.

Example 2

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]

The newcomer joins [3,5] and [6,7], then touches [8,10] at 8. Closed endpoints make that contact an overlap, yielding [3,10].

Example 3

Input: intervals = [], newInterval = [5,5]
Output: [[5,5]]

With no existing blocks, the point interval is the entire answer. Its endpoints may be equal, and the returned row is a copy.

Example 4

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

The newcomer touches the first block at 3 and the second at 6, connecting both into one closed block.

Example 5

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

The newcomer is already contained in the existing interval, so the covered region stays [1,9].

Intuition

Sorted, non-overlapping input splits around the newcomer into three regions: intervals entirely before it, intervals absorbed into it, and intervals entirely after it. In Example 1, [1,3] overlaps [2,5], widening the pending block to [1,5]; [6,9] then lies wholly after that block. There is no need to reorder the input or compare every pair. Because endpoints are included, [1,3] and [3,5] must merge; a strict gap is required to keep two blocks apart.

Approaches

Append Sort Merge

Solution Details

Reveal Append Sort Merge: intuition, complexity, and code

Intuition

Appending the new interval reduces the task to the classic merge-all-overlaps problem, which sorting plus one linear merge always solves. The extra sort is pure overhead, since the input order is already nearly perfect.

Step-by-Step Logic

Create an outer list containing references to the existing rows and newcomer, then sort that new list by start. Example 1 becomes [[1,3],[2,5],[6,9]]; neither input is reordered.
Seed the result with a copied first row. For each remaining interval compare its start with the last result end. Example 1 seeds [1,3].
If the start is at most that end, widen only the result row. Example 1 merges [2,5] into [1,3], changing its end from 3 to 5.
Otherwise append a new row containing the interval endpoints. Example 1 appends [6,9]; return [[1,5],[6,9]]. Copy every emitted row so the result shares no mutable row with an argument.

Why It Works

After sorting, all future intervals begin at or after the current one. Maintain that the result contains the exact union of the processed intervals, in sorted disjoint blocks. A new start no larger than the last result end overlaps that block, and replacing the end by the larger endpoint preserves its union. A start strictly beyond the last end leaves a real gap and must begin a separate block. Earlier result blocks cannot overlap the new interval because their ends precede the last block start. Induction over the sorted rows therefore produces exactly the required union, and copying output rows changes ownership without changing endpoints.

Dry Run

Append Sort Merge: variable states at each step
action	current row	last block before → after	result
append and sort outer copy	none	none	ordered `[[1,3],[2,5],[6,9]]`, result `[]`
seed copied row	`[1,3]`	none → `[1,3]`	`[[1,3]]`
`2 <= 3`, merge	`[2,5]`	`[1,3]` → `[1,5]`	`[[1,5]]`
`6 > 5`, append copy	`[6,9]`	`[1,5]` → `[6,9]`	`[[1,5],[6,9]]`
finish	none	unchanged	return `[[1,5],[6,9]]`

Complexity Analysis

Time Complexity

O((n+1) \log(n+2))

Space Complexity

O(n+1)

Let n be the number of existing intervals. Sorting n + 1 row references takes at most O((n + 1) log(n + 2)) time, followed by n + 1 merge visits; the shifted expression includes empty input. The outer working copy, sorting workspace and newly allocated result rows each use O(n + 1) space. Temporary input references are read-only; every output row is copied. Python avoids slicing the sorted tail.

Code

Solution.java

1import java.util.ArrayList;2import java.util.Arrays;3import java.util.List;4
5class Solution {6    public int[][] insert(int[][] intervals, int[] newInterval) {7        int[][] all = new int[intervals.length + 1][];8        for (int i = 0; i < intervals.length; i++) {9            all[i] = intervals[i];10        }11        all[intervals.length] = newInterval;12        // Sort only the outer working copy; input rows remain read-only.13        Arrays.sort(all, (a, b) -> Integer.compare(a[0], b[0]));14        List<int[]> res = new ArrayList<>();15        res.add(new int[]{all[0][0], all[0][1]});16        for (int i = 1; i < all.length; i++) {17            int[] last = res.get(res.size() - 1);18            // Closed intervals overlap even when their endpoints are equal.19            if (all[i][0] <= last[1]) {20                last[1] = Math.max(last[1], all[i][1]);21            } else {22                res.add(new int[]{all[i][0], all[i][1]});23            }24        }25        return res.toArray(new int[res.size()][]);26    }27}

Hints

Hint 1

Every existing interval is either fully left of the new one, fully right of it, or overlapping it.

Hint 2

Overlapping intervals never need to be emitted immediately: fold them into the new interval bounds instead.

Hint 3

Once an interval starts strictly after the folded new interval ends, emit the new interval first and copy the rest untouched.

Edge Cases

An empty intervals list returns just [newInterval].
A newInterval touching an endpoint, such as [3,5] against [1,3], still overlaps and merges into [1,5].
A newInterval spanning everything collapses the whole list into a single interval.

Common Mistakes and Interview Tips

Treating touching closed endpoints as a gap: [1,3] and [3,5] share point 3 and must merge.
Forgetting the final pending append loses the newcomer when it belongs after every input row or when input is empty.
Appending a borrowed input row or setting pending directly to an input row makes later result mutation change an argument. Copy every emitted or carried row.
Sorting the original outer list mutates its order; the sorting baseline sorts a separate outer copy.

Key Takeaway

Sorted input turns insertion into one linear pass: everything left is copied, everything overlapping is folded, and everything right is copied after the folded interval is emitted.