Grind 75 Question 26: Insert Interval

My first merge interval problem!

The Question

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.

The Initial Attempts

So, as I mentioned above — I know this is a merge interval problem. I mean, it’s in the name! But I’ve never done one before, so I don’t know exactly how to efficiently code it up. My initial attempt doesn’t pass muster and won’t debug, but I think it’s because I’m trying to set a new value in the array instead of using Array.splice().

/**
 * @param {number[][]} intervals
 * @param {number[]} newInterval
 * @return {number[][]}
 */
var insert = function(intervals, newInterval) {
    
	for(i = 0; i > intervals.length; i++){
		if (intervals[i][0] < newInterval[0] && intervals[i+1][0] > newInterval[0]){
			if(intervals[i][1] > newInterval[0]){
				intervals[i][1] = newInterval[0]
}
if(intervals[i+1][0] < newInterval[1]){
	Intervals[i+1][0] = newInterval[1]
} else intervals.splice(i+1, 1)
		}
	}
	return intervals;
};

I step away from my computer and Jarrod steals it, so I move to the lil computer and re-code it within the Leetcode IDE. (Did I use IDE right there?) After some tweaking, my new code runs and passes…until I submit it and it gets tripped up on edge cases.

var insert = function(intervals, newInterval) {
    if (intervals.length == 0) intervals.push(newInterval)
    
    for(i = 0; i< intervals.length -1; i++){
        if (intervals[i][1] < newInterval[0] && intervals[i+1][0] > newInterval[1]){
            intervals.splice(i+1, 1, newInterval)
        }
        if(intervals[i][0] < newInterval[0] && intervals[i][1] > newInterval[0]){
            intervals[i].splice(1, 1, newInterval[1]);
        }
        if(intervals[i][1] >= intervals[i+1][1]){
            intervals.splice(i+1, 1)
        }
        if(intervals[i][1] >= intervals[i+1][0]){
            intervals[i].splice(1, 1, intervals[i+1][1]);
            intervals.splice(i+1, 1);
        }
    }
    return intervals;
};

Bleh. So off to Neetcode I go, to finish the video and see his code.

The Solution

Neetcode helped, but did not help at the same time. His Python solution helped me get 90% of the way there, but Python has some fancy built-in stuff that I couldn’t utilize with Javascript, so I had to look up a forum-dweller’s generous answer.

var insert = function(intervals, newInterval) {
    const merged = [];
    let i = 0;
    let start = newInterval[0];
    let end = newInterval[1]
    
    while(i < intervals.length && intervals[i][1] < start){
        merged.push(intervals[i]);
        i++;
    }
    
    while (i < intervals.length && intervals[i][0] <= end) {
        start = Math.min(start, intervals[i][0]);
        end = Math.max(end, intervals[i][1]);
        i++;
    }
    
    merged.push([start, end]);
    
    while (i < intervals.length) {
        merged.push(intervals[i]);
        i++;
    }
    return merged;
};

Here’s the gist of it:

1. Create a bunch of variables. An empty merged array to return, an i for iterating, and — very important here — a “start” and “end”, which is a brilliant way to get around continually splicing and dicing — something I was trying to do in my solution. You’ll see.
2. So then we look over each element in the intervals array to see if it meets certain qualifications:
   1. If the end of interval i is less than the start of the interval to be merged, push interval i into the new merged array — since it doesn’t overlap in any way and is before the interval to be merged in.
   2. If the start of intervals i is less than the end of the merge interval, find the min between the 0 elements and the max between the 1 element. This means that if it’s a non-overlapping interval like [2, 3] and [5, 6], start and end will remain the same. But if it is an overlapping interval, like [2, 6] and [3, 7], the resulting start-end element will be [2, 7].
   3. That second bit essentially runs until the end of the merge interval is reached. The new element is created from start, end (BRILLIANT, I tell you) and pushed into the new array.
3. Finally, the remaining elements are pushed in and the new array is returned. Voila!

What I Learned

So, I struggled hard with this one. It’s 8:33 pm — I spent way too long on this one problem today. Bad timeboxing, Em! But I did learn a lot; namely:

1. Merge intervals! My first problem with it!
2. Avoid continual splicing and ensuing confusion by just creating two variables and pushing them at the last minute. So smart.

Related Posts

F

Five Things for May 10

A

April Recap, May Intentions

F

Five Things for April 26