Insert Interval

NeetCode: Insert Interval · LeetCode: 57. Insert Interval · Difficulty: Medium

You are given an array of non-overlapping intervals [start, end] sorted by start, and a newInterval. Insert it so the array stays sorted and non-overlapping, merging any intervals that overlap it (touching endpoints count as overlapping).

Example

Text

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

Brute force: append, sort, merge

Add the new interval to a list, sort by start, and run the standard merge sweep (see Merge Intervals). This ignores that the input is already sorted, so the sort costs O(n log n). The sweep keeps a List<int[]> of merged intervals and either widens the last one or appends a new one. toArray(new int[0][]) converts the list to the int[][] that the method returns.

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[] iv : all) {
            if (!merged.isEmpty() && iv[0] <= merged.get(merged.size() - 1)[1]) {
                int[] last = merged.get(merged.size() - 1);
                last[1] = Math.max(last[1], iv[1]);
            } else {
                merged.add(new int[] {iv[0], iv[1]});
            }
        }
        return merged.toArray(new int[0][]);
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(Arrays.deepToString(solution.insert(new int[][] {{1, 3}, {4, 6}}, new int[] {2, 5})));
        System.out.println(Arrays.deepToString(solution.insert(
                new int[][] {{1, 2}, {3, 5}, {6, 7}, {8, 10}, {12, 16}}, new int[] {4, 8})));
        System.out.println(Arrays.deepToString(solution.insert(new int[][] {}, new int[] {5, 7})));
    }
}

Output

[[1, 6]]
[[1, 2], [3, 10], [12, 16]]
[[5, 7]]

The merge step copies each interval into a new array before widening it, so the caller's arrays are not modified. Time: O(n log n). Space: O(n).

Optimal: one linear pass in three phases

Because the input is sorted and disjoint, the intervals split into three groups relative to the new one:

Intervals that end before the new interval starts (end < new.start): copy them unchanged.
Intervals that overlap it (start <= new.end): absorb them by widening the new interval to min of the starts and max of the ends.
Intervals that start after it: copy them unchanged.

Push the merged new interval between phase 1 and phase 3. One index i moves through the array across all three loops.

Java

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

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> result = new ArrayList<>();
        int start = newInterval[0];
        int end = newInterval[1];
        int i = 0;
        int n = intervals.length;
        // 1. intervals entirely before the new one
        while (i < n && intervals[i][1] < start) {
            result.add(intervals[i++]);
        }
        // 2. intervals overlapping the new one are absorbed into it
        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 entirely after the new one
        while (i < n) {
            result.add(intervals[i++]);
        }
        return result.toArray(new int[0][]);
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(Arrays.deepToString(solution.insert(new int[][] {{1, 3}, {4, 6}}, new int[] {2, 5})));
        System.out.println(Arrays.deepToString(solution.insert(
                new int[][] {{1, 2}, {3, 5}, {6, 7}, {8, 10}, {12, 16}}, new int[] {4, 8})));
        System.out.println(Arrays.deepToString(solution.insert(new int[][] {}, new int[] {5, 7})));
    }
}

Output

[[1, 6]]
[[1, 2], [3, 10], [12, 16]]
[[5, 7]]

Phases 1 and 3 add the original int[] objects to the result, so the result shares them with the input. Time: O(n). Space: O(n) for the output, O(1) extra.