Insert Interval (LC 57): One-Pass Merge

Insert a new interval into a sorted list of non-overlapping intervals and merge any overlaps. One linear pass copies intervals before it, merges the overlapping ones, then copies the rest. O(n) time.

Language Selection

Choose your preferred programming language

Showing: Python

Insert Interval

Problem Statement

You have a list of closed intervals, intervals, where each entry is [start, end]. The intervals do not overlap each other and are listed in increasing order of start.

You also get one more interval, newInterval = [start, end]. Add it to the list so that the result is still sorted by start and still has no overlapping intervals. Wherever the new interval overlaps existing ones, combine them into a single interval that covers all of them.

Two intervals that share an endpoint, such as [1, 4] and [4, 6], count as overlapping and must be combined into [1, 6].

Return the resulting list. You may build a new list rather than editing the input in place.

Examples

Example 1:

Input: intervals = [[2,4],[7,9],[12,15]], newInterval = [5,6]
Output: [[2,4],[5,6],[7,9],[12,15]]
Explanation: [5,6] fits in the gap between [2,4] and [7,9] without touching either.

Example 2:

Input: intervals = [[1,3],[4,6],[8,10],[11,14]], newInterval = [5,11]
Output: [[1,3],[4,14]]
Explanation: [5,11] overlaps [4,6] and [8,10], and touches [11,14] at 11. All four combine into [4,14].

Example 3:

Input: intervals = [], newInterval = [3,8]
Output: [[3,8]]
Explanation: With nothing to merge, the new interval is the whole answer.

Constraints

  • 0 <= intervals.length <= 10^4
  • intervals[i].length == 2
  • 0 <= start_i <= end_i <= 10^5
  • intervals is sorted by start_i in ascending order and has no overlapping intervals.
  • newInterval.length == 2
  • 0 <= start <= end <= 10^5

Approach 1: Append, Sort, and Merge

Algorithm

If you already know Merge Intervals (LC 56), the quickest correct answer reuses it: add the new interval to the list, sort by start, and merge. It ignores the fact that the input is already sorted, so it is slower than necessary.

  1. Put all intervals plus newInterval into one list.
  2. Sort the list by start.
  3. Walk the list. If the current interval starts at or before the end of the last merged interval, extend that end. Otherwise start a new merged interval.

New arrays are created for the merged output, so extending an end never changes the caller’s input intervals.

Implementation

Python:

from typing import List


class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        merged = []
        for start, end in sorted(intervals + [newInterval]):
            if merged and start <= merged[-1][1]:
                # Overlaps (or touches) the last merged interval: extend it
                merged[-1][1] = max(merged[-1][1], end)
            else:
                merged.append([start, end])  # fresh list, input stays untouched
        return merged

Java:

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

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int[][] all = Arrays.copyOf(intervals, intervals.length + 1);
        all[intervals.length] = newInterval;
        Arrays.sort(all, (a, b) -> Integer.compare(a[0], b[0]));

        List<int[]> merged = new ArrayList<>();
        for (int[] cur : all) {
            if (!merged.isEmpty() && cur[0] <= merged.get(merged.size() - 1)[1]) {
                // Overlaps (or touches) the last merged interval: extend it
                int[] last = merged.get(merged.size() - 1);
                last[1] = Math.max(last[1], cur[1]);
            } else {
                merged.add(new int[] {cur[0], cur[1]}); // copy, input stays untouched
            }
        }
        return merged.toArray(new int[0][]);
    }
}

Go:

import "sort"

func insert(intervals [][]int, newInterval []int) [][]int {
    all := make([][]int, 0, len(intervals)+1)
    all = append(all, intervals...)
    all = append(all, newInterval)
    sort.Slice(all, func(i, j int) bool { return all[i][0] < all[j][0] })

    merged := [][]int{}
    for _, cur := range all {
        if n := len(merged); n > 0 && cur[0] <= merged[n-1][1] {
            // Overlaps (or touches) the last merged interval: extend it
            merged[n-1][1] = max(merged[n-1][1], cur[1])
        } else {
            merged = append(merged, []int{cur[0], cur[1]}) // copy, input stays untouched
        }
    }
    return merged
}

JavaScript:

/**
 * @param {number[][]} intervals
 * @param {number[]} newInterval
 * @return {number[][]}
 */
var insert = function(intervals, newInterval) {
    const all = [...intervals, newInterval].sort((a, b) => a[0] - b[0]);
    const merged = [];
    for (const [start, end] of all) {
        const last = merged[merged.length - 1];
        if (last && start <= last[1]) {
            // Overlaps (or touches) the last merged interval: extend it
            last[1] = Math.max(last[1], end);
        } else {
            merged.push([start, end]); // copy, input stays untouched
        }
    }
    return merged;
};

C#:

using System;
using System.Collections.Generic;

public class Solution {
    public int[][] Insert(int[][] intervals, int[] newInterval) {
        var all = new List<int[]>(intervals) { newInterval };
        all.Sort((a, b) => a[0].CompareTo(b[0]));

        var merged = new List<int[]>();
        foreach (var cur in all) {
            if (merged.Count > 0 && cur[0] <= merged[^1][1]) {
                // Overlaps (or touches) the last merged interval: extend it
                merged[^1][1] = Math.Max(merged[^1][1], cur[1]);
            } else {
                merged.Add(new[] { cur[0], cur[1] }); // copy, input stays untouched
            }
        }
        return merged.ToArray();
    }
}

C++:

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> all = intervals;  // work on a copy
        all.push_back(newInterval);
        sort(all.begin(), all.end(),
             [](const vector<int>& a, const vector<int>& b) { return a[0] < b[0]; });

        vector<vector<int>> merged;
        for (const auto& cur : all) {
            if (!merged.empty() && cur[0] <= merged.back()[1]) {
                // Overlaps (or touches) the last merged interval: extend it
                merged.back()[1] = max(merged.back()[1], cur[1]);
            } else {
                merged.push_back(cur);
            }
        }
        return merged;
    }
};

Complexity Analysis

  • Time: O(n log n) for the sort, where n is the number of intervals. The merge pass is O(n).
  • Space: O(n) for the combined list and the output (plus the sort’s own working memory).

Approach 2: Single Linear Pass (Optimal)

Algorithm

Because the input is already sorted and non-overlapping, the intervals fall into three consecutive groups relative to newInterval = [s, e]:

  1. Entirely before it: intervals whose end is less than s. Copy them to the output unchanged.
  2. Overlapping it: intervals whose start is at most e (and which were not in group 1). Absorb each one by widening s = min(s, start) and e = max(e, end).
  3. Entirely after it: everything left. Append the merged [s, e], then copy the rest unchanged.

A single index walks through the three groups in order, so every interval is looked at exactly once.

Implementation

Python:

from typing import List


class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        result = []
        i, n = 0, len(intervals)
        start, end = newInterval

        # 1. Intervals that end before the new one starts
        while i < n and intervals[i][1] < start:
            result.append(intervals[i])
            i += 1

        # 2. Intervals that overlap the new one: absorb them
        while i < n and intervals[i][0] <= end:
            start = min(start, intervals[i][0])
            end = max(end, intervals[i][1])
            i += 1
        result.append([start, end])

        # 3. Intervals that start after the merged one ends
        result.extend(intervals[i:])
        return result

Java:

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

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

        // 1. Intervals that end before the new one starts
        while (i < n && intervals[i][1] < start) {
            result.add(intervals[i++]);
        }

        // 2. Intervals that overlap the new one: absorb them
        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][]);
    }
}

Go:

func insert(intervals [][]int, newInterval []int) [][]int {
    result := make([][]int, 0, len(intervals)+1)
    i, n := 0, len(intervals)
    start, end := newInterval[0], newInterval[1]

    // 1. Intervals that end before the new one starts
    for i < n && intervals[i][1] < start {
        result = append(result, intervals[i])
        i++
    }

    // 2. Intervals that overlap the new one: absorb them
    for i < n && intervals[i][0] <= end {
        start = min(start, intervals[i][0])
        end = max(end, intervals[i][1])
        i++
    }
    result = append(result, []int{start, end})

    // 3. Intervals that start after the merged one ends
    return append(result, intervals[i:]...)
}

JavaScript:

/**
 * @param {number[][]} intervals
 * @param {number[]} newInterval
 * @return {number[][]}
 */
var insert = function(intervals, newInterval) {
    const result = [];
    const n = intervals.length;
    let i = 0;
    let [start, end] = newInterval;

    // 1. Intervals that end before the new one starts
    while (i < n && intervals[i][1] < start) {
        result.push(intervals[i++]);
    }

    // 2. Intervals that overlap the new one: absorb them
    while (i < n && intervals[i][0] <= end) {
        start = Math.min(start, intervals[i][0]);
        end = Math.max(end, intervals[i][1]);
        i++;
    }
    result.push([start, end]);

    // 3. Intervals that start after the merged one ends
    while (i < n) {
        result.push(intervals[i++]);
    }
    return result;
};

C#:

using System;
using System.Collections.Generic;

public class Solution {
    public int[][] Insert(int[][] intervals, int[] newInterval) {
        var result = new List<int[]>(intervals.Length + 1);
        int i = 0, n = intervals.Length;
        int start = newInterval[0], end = newInterval[1];

        // 1. Intervals that end before the new one starts
        while (i < n && intervals[i][1] < start) {
            result.Add(intervals[i++]);
        }

        // 2. Intervals that overlap the new one: absorb them
        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[] { start, end });

        // 3. Intervals that start after the merged one ends
        while (i < n) {
            result.Add(intervals[i++]);
        }
        return result.ToArray();
    }
}

C++:

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> result;
        result.reserve(intervals.size() + 1);
        size_t i = 0, n = intervals.size();
        int start = newInterval[0], end = newInterval[1];

        // 1. Intervals that end before the new one starts
        while (i < n && intervals[i][1] < start) {
            result.push_back(intervals[i++]);
        }

        // 2. Intervals that overlap the new one: absorb them
        while (i < n && intervals[i][0] <= end) {
            start = min(start, intervals[i][0]);
            end = max(end, intervals[i][1]);
            i++;
        }
        result.push_back({start, end});

        // 3. Intervals that start after the merged one ends
        while (i < n) {
            result.push_back(intervals[i++]);
        }
        return result;
    }
};

Complexity Analysis

  • Time: O(n). Each interval is visited once across the three loops.
  • Space: O(n) for the output list. Apart from the output, only a few variables are used, so the extra space is O(1).

Key Insights

  1. Use the sorted input: the existing intervals are already in order and disjoint, so there is no need to sort. That is what turns O(n log n) into O(n).
  2. Three groups, in order: before, overlapping, after. Once you see that the overlapping intervals form one contiguous block, the code is three simple loops.
  3. Two different tests: “before” means end < newStart, and “overlapping” means start <= newEnd. Using strict and non-strict comparisons this way makes touching intervals merge.
  4. Grow the new interval, not the old ones: keep start and end in local variables and widen them. The output gets one fresh interval for the merged block.

Edge Cases

  1. Empty list: the answer is just [newInterval].
  2. New interval before everything: [[5,7]] with [1,2] gives [[1,2],[5,7]]. Group 1 is empty and nothing overlaps.
  3. New interval after everything: [[5,7]] with [8,9] gives [[5,7],[8,9]].
  4. Touching endpoints: [[5,7]] with [7,9] gives [[5,9]], and with [3,5] gives [[3,7]].
  5. Swallows everything: [[1,2],[3,4]] with [0,100000] gives [[0,100000]].
  6. Fully inside an existing interval: [[1,5]] with [2,3] gives [[1,5]].
  7. Zero-length intervals: [[0,0]] with [0,0] gives [[0,0]].

Common Mistakes

  1. Using <= in the first loop: intervals[i][1] <= start would treat a touching interval like [3,5] with new [5,8] as separate, leaving [[3,5],[5,8]] instead of [[3,8]].
  2. Forgetting to append the merged interval: it must be added after the overlap loop even when nothing overlapped.
  3. Only widening the end: the first overlapping interval can start before newInterval, so update start with min as well.
  4. Mutating input arrays while merging: in the sort-based version, appending an input interval to the output and then extending its end silently changes the caller’s data. Copy before you modify.
  5. Inserting into the input array in the middle: shifting elements on every insert or delete makes the solution O(n^2) in the worst case.

Interview Tips

  1. Point out the sorted input early: it tells the interviewer you are looking for the O(n) solution, not just reusing Merge Intervals.
  2. Clarify touching intervals: ask whether [1,4] and [4,6] should merge. For this problem they do.
  3. Walk through the three phases on an example: it makes the loop conditions easy to justify.
  4. Mention binary search as an option: you can find where group 2 starts and ends in O(log n), but building the output is still O(n), so the total does not improve.

Follow-up Questions

  1. What if the input were unsorted? Fall back to sort-then-merge, O(n log n).
  2. Many insertions over time? Keep the intervals in a balanced tree or sorted map keyed by start, so each insertion finds and merges its neighbors in O(log n + k), where k is the number of intervals merged.
  3. Remove an interval instead? Walk the list and split any interval that partly overlaps the removed range (LC 1272, Remove Interval).
  4. Can you do it in place? In languages with dynamic arrays, you can overwrite the overlapping block with the merged interval and delete the rest, but deletions shift elements, so it stays O(n).