Back to DSA

Insert Interval

hard
Acceptance: 36%
IntervalsArrays

You have a sorted list of non-overlapping intervals and a new interval to add. Insert the new interval into the list, merging with any existing intervals that it overlaps, and return the updated sorted list.

Examples

Example 1:
Input:intervals = [[2,4],[7,10]], newInterval = [3,8]
Output:[[2,10]]
Example 2:
Input:intervals = [[1,2],[4,6],[8,10],[13,17]], newInterval = [5,9]
Output:[[1,2],[4,10],[13,17]]

Hints

Related Problems

Remove Duplicates from Sorted ArrayeasyBest Time to Buy and Sell StockeasyTwo SumeasyMerge Sorted ArrayeasyMove Zeroeseasy
00:00
import java.util.*;

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