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.

Image for post
Image for post

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

Image for post
Image for post
//FIND BEGINNING OF NEW RANGEfor (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 RANGEfor (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.

Written by

After years of teaching music in Austin, Shanghai and Yangon, I’m making a career change to my other passion, software development.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store