130.Insert Interval

MediumBlind 75Intervals · 1/6

Problem

You are given an array of non-overlapping intervals intervals, sorted in ascending order by start, where intervals[i] = [start_i, end_i], and a new interval newInterval = [start, end].

Insert newInterval so that the result is still sorted by start and still non-overlapping, merging any intervals that overlap with it. Return the resulting array. Intervals that touch ([1,2] and [2,3]) count as overlapping.

Examples

Input:  intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
Explanation: [2,5] overlaps [1,3] -> merged into [1,5].

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

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

Constraints

0 <= intervals.length <= 10^4
intervals[i].length == 2, 0 <= start_i <= end_i <= 10^5
intervals is sorted by start_i and contains no overlaps.
newInterval.length == 2, 0 <= start <= end <= 10^5

💡 Key Insight

Because the input is already sorted and disjoint, every existing interval falls into exactly one of three groups relative to newInterval: entirely before it (end < newStart), overlapping it, or entirely after it (start > newEnd). These groups are contiguous, so one left-to-right pass copies the first group, folds the middle group into newInterval with min/max, and copies the rest.

Brute Force (Append, Sort, Merge)

TimeO(n log n)SpaceO(n)

Intuition

Ignore the fact that the input is sorted: add newInterval to the list, sort everything by start, and run the standard "merge intervals" sweep.

Algorithm

Copy intervals into a list and add newInterval.
Sort by start.
Sweep: if the current interval starts after the last merged end, append it; otherwise extend the last merged end with max.

Visualization

[[1,3],[6,9]] + [2,5] -> sort -> [[1,3],[2,5],[6,9]]
merge: [1,3] ; [2,5] overlaps (2 <= 3) -> [1,5] ; [6,9] starts after 5 -> append
result [[1,5],[6,9]]

Code

java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> all = new ArrayList<>(Arrays.asList(intervals));
        all.add(newInterval);
        all.sort((a, b) -> Integer.compare(a[0], b[0]));
        List<int[]> merged = new ArrayList<>();
        for (int[] cur : all) {
            if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < cur[0]) {
                merged.add(new int[] {cur[0], cur[1]}); // gap: new block
            } else {
                int[] last = merged.get(merged.size() - 1);
                last[1] = Math.max(last[1], cur[1]); // overlap: extend
            }
        }
        return merged.toArray(new int[0][]);
    }
}

Complexity

Time: O(n log n) — the sort dominates.
Space: O(n) — the copied and merged lists.

Binary Search Position, Then Merge

TimeO(n)SpaceO(n)

Intuition

The array is already sorted, so we can find where newInterval belongs by binary search on start values instead of sorting. After inserting it at that position, the list is sorted, and a single merge sweep finishes the job.

Algorithm

Binary-search the first index pos with intervals[pos][0] > newInterval[0].
Build a list: intervals[0..pos), then newInterval, then intervals[pos..n).
Run the same merge sweep as Approach 1.

Visualization

starts = [1,3,6,8,12], newStart = 4
binary search -> pos = 2 (first start > 4 is 6)
list: [1,2] [3,5] [4,8] [6,7] [8,10] [12,16]
merge: [1,2] | [3,5]+[4,8]+[6,7]+[8,10] -> [3,10] | [12,16]

Code

java

import java.util.ArrayList;
import java.util.List;

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int lo = 0, hi = intervals.length;
        while (lo < hi) { // first index whose start > newInterval start
            int mid = (lo + hi) >>> 1;
            if (intervals[mid][0] <= newInterval[0]) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        List<int[]> ordered = new ArrayList<>();
        for (int i = 0; i < lo; i++) {
            ordered.add(intervals[i]);
        }
        ordered.add(newInterval);
        for (int i = lo; i < intervals.length; i++) {
            ordered.add(intervals[i]);
        }
        List<int[]> merged = new ArrayList<>();
        for (int[] cur : ordered) {
            if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < cur[0]) {
                merged.add(new int[] {cur[0], cur[1]});
            } else {
                int[] last = merged.get(merged.size() - 1);
                last[1] = Math.max(last[1], cur[1]);
            }
        }
        return merged.toArray(new int[0][]);
    }
}

Complexity

Time: O(n) — O(log n) search, then linear copy and merge.
Space: O(n) — the intermediate list and output.

Single Linear PassOptimal

TimeO(n)SpaceO(n)

Intuition

Skip the intermediate list entirely. Walk once with index i:

While intervals[i] ends before newInterval starts, it cannot overlap — copy it.
While intervals[i] starts at or before newInterval's (growing) end, it overlaps — absorb it by widening newInterval.
Emit the merged newInterval, then copy everything left.

Algorithm

i = 0. While i < n and intervals[i][1] < newStart: add intervals[i++].
While i < n and intervals[i][0] <= newEnd: newStart = min(...), newEnd = max(...), i++.
Add [newStart, newEnd].
Add the remaining intervals[i..n).

Dry Run

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

flowchart LR
    A["[1,2]<br/>2 < 4: before"] -->|"copy"| B["[3,5]<br/>3 <= 8: overlap<br/>new = [3,8]"]
    B --> C["[6,7]<br/>6 <= 8: overlap<br/>new = [3,8]"]
    C --> D["[8,10]<br/>8 <= 8: overlap<br/>new = [3,10]"]
    D --> E["[12,16]<br/>12 > 10: stop merging"]
    E --> F["emit [3,10], copy [12,16]"]

point:      0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16
existing:      [--]  [-----]  [--]  [-----]     [-----------]
new:                    [-----------]
result:        [--]  [--------------------]     [-----------]

Code

java

import java.util.ArrayList;
import java.util.List;

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

        // 1) intervals that finish before the new one starts
        while (i < n && intervals[i][1] < start) {
            result.add(intervals[i++]);
        }
        // 2) intervals that overlap: grow [start, end]
        while (i < n && intervals[i][0] <= end) {
            start = Math.min(start, intervals[i][0]);
            end = Math.max(end, intervals[i][1]);
            i++;
        }
        result.add(new int[] {start, end});
        // 3) intervals that start after the merged one ends
        while (i < n) {
            result.add(intervals[i++]);
        }
        return result.toArray(new int[0][]);
    }
}

Complexity

Time: O(n) — each interval is visited once.
Space: O(n) — the output list (O(1) extra besides it).

Complexity Comparison

Approach	Time	Space
Append, Sort, Merge	O(n log n)	O(n)
Binary Search + Merge	O(n)	O(n)
Single Linear Pass	O(n)	O(n)

Common Pitfalls

Using <= in the "before" check (intervals[i][1] <= start) — touching intervals like [1,2] and [2,5] must merge.
Comparing overlapping intervals against the original newInterval end instead of the growing end.
Forgetting to add the merged interval when it lies after all existing intervals (or when intervals is empty).
Mutating input arrays while also returning them in the result — create a new array for the merged interval.