algoadvance

Leetcode 57. Insert Interval

Problem Statement

You are given an array of non-overlapping intervals intervals where intervals[i] = [start_i, end_i], representing the start and the end of the i-th interval, and intervals is sorted in ascending order by start_i. You are also given an interval newInterval = [start, end] that represents the new interval to be inserted into intervals.

Insert newInterval into intervals such that the intervals still remain non-overlapping and sorted in ascending order by start time.

Return the resulting array of intervals after the insertion.

Example

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

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

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

Clarifying Questions

  1. What should be returned if intervals array is empty?
    • Return the list containing only the new interval.
  2. Are the intervals always sorted initially?
    • Yes, the intervals are given to be sorted initially.
  3. Can the new interval be already contained inside an existing interval?
    • Yes, and it still has to be correctly merged without duplicates.
  4. Can the new interval overlap multiple existing intervals?
    • Yes, all overlapping intervals should be merged into a single interval.
  5. How to handle intervals that don’t overlap at all with the new interval?
    • They should remain in their original position without any change.

Strategy

  1. Traverse the given intervals.
  2. Add all intervals ending before the newInterval starts to the result list.
  3. Merge all intervals that overlap with newInterval. This can be done by updating newInterval to the minimum start and maximum end of the overlapping intervals.
  4. Add the merged newInterval to the result.
  5. Add all remaining intervals to the result.

Time Complexity

The time complexity of this approach is (O(n)), where (n) is the number of intervals in the input list. This is because each interval is processed at most twice – once to check for non-overlapping periods and once to either merge or append to the result list.

Code

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

public class InsertInterval {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> result = new ArrayList<>();
        int i = 0;
        int n = intervals.length;
        
        // Add all intervals ending before newInterval starts
        while (i < n && intervals[i][1] < newInterval[0]) {
            result.add(intervals[i]);
            i++;
        }
        
        // Merge all overlapping intervals with newInterval
        while (i < n && 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);
        
        // Add all intervals starting after newInterval ends
        while (i < n) {
            result.add(intervals[i]);
            i++;
        }
        
        return result.toArray(new int[result.size()][]);
    }
}

This code should successfully merge any newInterval into the existing sorted, non-overlapping intervals.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI