☕ DSA Java Articles

Topics › Greedy Algorithms › Medium/Hard

Insert Interval

Medium TUF ID 546 A2ZBlind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given a list of closed intervals intervals[i] = [start_i, end_i] that is sorted by start and whose intervals are pairwise non-overlapping. You are also given one more interval, newInterval. Insert it so that the list stays sorted and non-overlapping, merging it with every interval it overlaps. Two closed intervals overlap when they share at least one point, so [1, 2] and [2, 3] merge into [1, 3]. Return the new list (a fresh array is fine).

Constraints: 0 ≤ n ≤ 10^4, 0 ≤ start_i ≤ end_i ≤ 10^5, and the same bounds for newInterval.

Example 1

intervals = [[1, 3], [6, 9]], newInterval = [2, 5]
answer = [[1, 5], [6, 9]]

[2, 5] overlaps [1, 3], so they merge into [1, 5]. It ends before [6, 9] starts, so that one is untouched.

Example 2

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

[4, 8] overlaps [3, 5], [6, 7] and [8, 10] (it touches 8), and the four together become [3, 10].

Approach 1: Brute force, append and merge everything

Intuition. If we did not know the list was sorted, we would solve the general “merge intervals” problem: throw the new interval into the pile, sort by start, and sweep once, either extending the last merged block or starting a new one. That is correct for any input, so it is a safe baseline. It ignores the fact that the list is already sorted and disjoint, which is why it is slower than needed.

Algorithm.

  1. Copy all intervals plus newInterval into one array.
  2. Sort by start.
  3. Sweep: if the current interval starts after the last block ends, start a new block; otherwise extend the last block’s end to the larger of the two ends.
static int[][] bruteForce(int[][] intervals, int[] newInterval) {
    int n = intervals.length;
    int[][] all = new int[n + 1][];
    for (int i = 0; i < n; i++) all[i] = intervals[i].clone();
    all[n] = newInterval.clone();
    Arrays.sort(all, (x, y) -> Integer.compare(x[0], y[0]));
    List<int[]> res = new ArrayList<>();
    for (int[] cur : all) {
        if (res.isEmpty() || cur[0] > res.get(res.size() - 1)[1]) {
            res.add(cur);                                     // gap: start a new block
        } else {
            int[] last = res.get(res.size() - 1);
            last[1] = Math.max(last[1], cur[1]);              // overlap: stretch the last block
        }
    }
    return res.toArray(new int[0][]);
}

Complexity. Time O(n log n) for the sort; the sweep is O(n). Space O(n) for the copy and the output.

The copies (clone()) matter: the sweep mutates last[1], and without copying it would silently change the caller’s intervals.

Approach 2: Optimal, one pass in three phases

Intuition. Because the input is sorted and disjoint, both the starts and the ends increase along the list. Relative to newInterval = [start, end], every existing interval therefore falls into exactly one of three contiguous groups:

  1. Left group: intervals that end before start (end_i < start). They cannot touch the new interval, and they form a prefix of the list because ends increase.
  2. Overlap group: intervals that start at or before the current end (start_i ≤ end). Each one is absorbed: start becomes the smaller start and end the larger end. We compare against the growing end, so the merged interval keeps swallowing as long as the next interval touches it.
  3. Right group: everything after that starts beyond end. Since starts increase, once one interval starts past end, all later ones do too, and they are copied unchanged.

Between phases 2 and 3 we emit the merged interval, which lands exactly in its sorted position: everything before it ended earlier, everything after it starts later.

Algorithm.

  1. i = 0. While intervals[i] ends before start, copy it and advance.
  2. While intervals[i] starts at or before end, set start = min(start, s_i), end = max(end, e_i) and advance.
  3. Append [start, end].
  4. Copy the remaining intervals.
static int[][] optimal(int[][] intervals, int[] newInterval) {
    List<int[]> res = new ArrayList<>();
    int n = intervals.length, i = 0;
    int start = newInterval[0], end = newInterval[1];
    while (i < n && intervals[i][1] < start) {                // entirely to the left: no contact
        res.add(intervals[i].clone());
        i++;
    }
    while (i < n && intervals[i][0] <= end) {                 // overlaps or touches the growing new interval
        start = Math.min(start, intervals[i][0]);
        end = Math.max(end, intervals[i][1]);
        i++;
    }
    res.add(new int[]{start, end});
    while (i < n) {                                           // entirely to the right
        res.add(intervals[i].clone());
        i++;
    }
    return res.toArray(new int[0][]);
}

Dry run on example 2, newInterval = [4, 8]:

i interval test phase start, end afterwards
0 [1, 2] 2 < 4 copy (left) 4, 8
1 [3, 5] 3 ≤ 8 absorb 3, 8
2 [6, 7] 6 ≤ 8 absorb 3, 8
3 [8, 10] 8 ≤ 8 absorb 3, 10
- - - emit [3, 10] -
4 [12, 16] 12 > 10 copy (right) -

Result [[1, 2], [3, 10], [12, 16]].

Complexity. Time O(n): each interval is looked at once. Space O(n) for the output; the extra working space is O(1).

You could binary-search the boundaries of the overlap group in O(log n), but building the output still copies n intervals, so the total stays O(n). Binary search only helps if you are allowed to modify a structure in place, such as a balanced tree of intervals.

Edge cases and pitfalls