Coding problem · Medium · Intervals

Insert Interval

Medium Algorithms & data structures Seen at Google, LinkedIn, Meta

You are given non-overlapping intervals sorted by start, and a newInterval. Insert newInterval so the list stays sorted and non-overlapping (merge where necessary) and return it.

Example 1

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

Example 2

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

Hints

Hint 1

Three phases: copy intervals that end before the new one starts, merge all that overlap it, copy the rest.

Write and run your solution

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the solution

Time O(n) · Space O(n)

Because the input is already sorted, a single pass suffices: append intervals entirely to the left, absorb overlapping ones into [min start, max end], append the merged interval, then append the rest. No sorting needed — O(n).

Reference solution

function insert(intervals, newInterval) {
  const out = [];
  let [s, e] = newInterval;
  let i = 0;
  while (i < intervals.length && intervals[i][1] < s) out.push(intervals[i++]);
  while (i < intervals.length && intervals[i][0] <= e) {
    s = Math.min(s, intervals[i][0]);
    e = Math.max(e, intervals[i][1]);
    i++;
  }
  out.push([s, e]);
  while (i < intervals.length) out.push(intervals[i++]);
  return out;
}

function insert(intervals: number[][], newInterval: number[]): number[][] {
  const out: number[][] = [];
  let [s, e] = newInterval;
  let i = 0;
  while (i < intervals.length && intervals[i][1] < s) out.push(intervals[i++]);
  while (i < intervals.length && intervals[i][0] <= e) {
    s = Math.min(s, intervals[i][0]);
    e = Math.max(e, intervals[i][1]);
    i++;
  }
  out.push([s, e]);
  return out.concat(intervals.slice(i));
}

def insert(intervals: list[list[int]], new_interval: list[int]) -> list[list[int]]:
    s, e = new_interval
    left = [iv for iv in intervals if iv[1] < s]
    right = [iv for iv in intervals if iv[0] > e]
    middle = [iv for iv in intervals if not (iv[1] < s or iv[0] > e)]
    if middle:
        s, e = min(s, middle[0][0]), max(e, middle[-1][1])
    return left + [[s, e]] + right

<?php

function insert(array $intervals, array $newInterval): array
{
    [$s, $e] = $newInterval;
    $out = [];
    $i = 0;
    $n = count($intervals);
    while ($i < $n && $intervals[$i][1] < $s) {
        $out[] = $intervals[$i++];
    }
    while ($i < $n && $intervals[$i][0] <= $e) {
        $s = min($s, $intervals[$i][0]);
        $e = max($e, $intervals[$i][1]);
        $i++;
    }
    $out[] = [$s, $e];
    return array_merge($out, array_slice($intervals, $i));
}

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> out = new ArrayList<>();
        int s = newInterval[0], e = newInterval[1], i = 0;
        while (i < intervals.length && intervals[i][1] < s) out.add(intervals[i++]);
        while (i < intervals.length && intervals[i][0] <= e) {
            s = Math.min(s, intervals[i][0]);
            e = Math.max(e, intervals[i][1]);
            i++;
        }
        out.add(new int[]{s, e});
        while (i < intervals.length) out.add(intervals[i++]);
        return out.toArray(new int[0][]);
    }
}

Merge Intervals · Medium
Find Free Meeting Slots · Medium