Leetcode problem 131 - Insert Interval

You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.

Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.

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]] Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

Constraints:

0 <= intervals.length <= 104 intervals[i].length == 2 0 <= starti <= endi <= 105 intervals is sorted by starti in ascending order. newInterval.length == 2 0 <= start <= end <= 105

/**
 * @param {number[][]} intervals
 * @param {number[]} newInterval
 * @return {number[][]}
 */
var insert = function (intervals, newInterval) {
  const result = [];
  let [newStart, newEnd] = newInterval;

  for (let [currStart, currEnd] of intervals) {
    if (currEnd < newStart) {
      result.push([currStart, currEnd]);
    } else if (currStart > newEnd) {
      result.push([newStart, newEnd]);
      [newStart, newEnd] = [currStart, currEnd];
    } else {
      newStart = Math.min(newStart, currStart);
      newEnd = Math.max(newEnd, currEnd);
    }
  }

  result.push([newStart, newEnd]);

  return result;
};

The time complexity of the provided solution is O(n), where n is the number of intervals in the input array. This is because the algorithm iterates through each interval in the intervals array once, performing constant-time operations within the loop. Thus, the time complexity grows linearly with the size of the input.

The space complexity of the solution is also O(n). This is because the result array may store up to n intervals in the worst case, where n is the number of intervals in the input array. Additionally, the variables used to store the newStart and newEnd coordinates require constant space, independent of the input size.