Insert Interval — LeetCode #57

Here’s my JavaScript solution to this popular challenge.

Input: A set of SORTED non-overlapping intervals (intervals) AND a new interval (newInterval).

Output: A new set of SORTED intervals that includes the new interval. If the new interval overlaps any of the other intervals, the intervals need to be merged.

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

Constraints: The set of intervals needs to be ordered, and there can be no overlapping.

First we can quickly determine if the following conditions are met:

1. If intervals set is empty, the function should immediately return newInterval — do not pass go, do not collect $100.

if (!intervals.length){
  return [newInterval]
}

2. If newInterval’s end is before the intervals’ first element’s start, then simply add the newInterval to the beginning of intervals. Likewise if newInterval’s beginning is before the intervals’ last element’s end, then simply add the newInterval to the end of intervals.

Dealing with the edge cases

if(newInterval[1] < intervals[0][0]){
  intervals.unshift(newInterval)
  return intervals
}
if(newInterval[0] > intervals[intervals.length-1][1])
  intervals.push(newInterval)
  return intervals
}

Now, with the low lying fruit picked, we need to find if and where our newInterval overlaps with intervals. Essentially we will be finding the overlap (if it exists) and replacing the original interval(s) with the new merged interval. Or, if there is no overlap, we will be simply adding the new interval in its correct position.

To do this we set up variables for both the position and indexes of the new, possibly merged interval:

idxBeg = 0;  //These variables are the indexes of the interval(s) 
idxEnd = 0;  // that will be replaced, or where newInterval needs
beg = 0;    //  to be placed. beg and end hold the actual range.
end = 0;

First we determine where the beginning of newInterval is positioned. We iterate from the beginning of intervals until we find an interval that either includes the start of newInterval OR starts after newInterval’s start. We remember the index of the interval and value of the lowest of the two.

Next we do the same with the the ending value, but this time we iterate backwards, starting from the end.

//FIND BEGINNING OF NEW RANGE
for (let i=0; i<intervals.length; i++) {
  if(intervals[i][0] <= newInterval[0] && intervals[i][1] >=  newInterval[0] ){
    idxBeg = i;
    beg = intervals[i][0]
    break
}
  if(intervals[i][0] > newInterval[0]){
    idxBeg = i
    beg = newInterval[0];
    break
  }
}
//FIND ENDING OF NEW RANGE
for (let i=intervals.length-1; i>=0; i--) {
  if(intervals[i][0] <= newInterval[1] && intervals[i][1] >= newInterval[1] ){
    idxEnd = i;
    end = intervals[i][1]
    break
  }
  if(intervals[i][0] < newInterval[1]){
    idxEnd = i
    end = newInterval[1];
    break
  }
}

Once we determine the range of the merged interval (if it needs to be merged), we just need to replace the range of intervals with the new merged interval using slice(beginning index, number to be replaced, the new merged interval):

const numOfIntervalsToDelete = idxEnd - idxBeg + 1;
intervals.splice(idxBeg, numOfIntervalsToDelete, [beg, end])
return intervals;

If no merging is necessary the numOfIntervalsToDelete will equal 0 and so none of the original intervals will be replaced and newInterval will be inserted in the correct location.

That’s it.