Insert Interval (LeetCode #57)

Image by La-Rel Easter on Unsplash

This article is part of a series from Nathan Thomas, a full stack software engineer working in San Francisco, CA. Other recent articles from him include Building Your Own Bitcoin Node and Unique Paths.

Introduction

If you’re looking for a quick walkthrough of an optimal solution to the LeetCode Insert Interval problem, you’re in the right spot.

This is a question in the Blind 75 LeetCode code challenge list, a group of questions put together by a tech lead at Facebook that’s been touted as a great way to prep for interviews.

Don’t beat yourself up too much if you’re here because it gave you a hard time. Everyone has a hard time with coding challenges sometimes.

Let’s get it started! 🙌🏻

Understanding the Problem 🕵🏻‍️

The first thing we should always try to do is understand all the rules for our challenge before writing a single line of code (see Polya’s Problem Solving Techniques):

1. We’ll be given a list of non-overlapping intervals called intervals
2. These intervals will have the shape of [start, end] with each of these values being an integer of 0 <= start <= end <= 105
3. The intervals list will be length of 0 <= intervals.length <= 104
4. We’ll also be given a new interval that we should insert into the intervals list, merging it with others if needed
5. We should merge existing intervals as well if they overlap
6. The existing intervals list will be sorted by start in ascending order
7. We should return this merged intervals list when we’re done

I’ll be using Python for the answer for this question since it’s a bit like a universal language — whether you prefer JavaScript, Java, Golang, C, or something else, everyone can “kind of” read Python.

We’ll also be jumping straight into an “optimal” solution. If you’re anything like me, you already attempted this problem before searching for an answer. I’m going to make sure you get a good one.

Okay. I think that’s enough housekeeping items for us to get started!

Initial Problem Setup 🏗

This problem extends the popular Merge Intervals problem with a new variation— in addition to merging intervals in a list that we’re given, we also need to insert a single additional new interval into the list as well.

This sounds complicated, and I’ll be real with you that it melted my brain a little bit the first time I did this one.

The first thing we need to do is set up our initial values. Additionally, the intervals list can be empty. If this is the case, we can just return the new_interval (which will always be defined). Here’s what this initial code looks like:

There’s our early return.

Next, we have an initialized output list that will end up holding our merge intervals. We can also destructure out the two values of new_interval once here and have them available for the rest of the problem when we do comparisons.

Finally, we have a boolean flag inserted to track if we’ve used the new_interval already.

Nice. I think we’re ready to get into some of the harder stuff.

Let’s do it. 🔥

Decision Trees and Intervals 🌲

First, we’re going to iterate over all of our intervals list:

For each current_interval here, we’re going to destructure off its current_start and current_end which the rules of the problem say will always be defined.

Next, we need to build a decision tree off the following rules:

1. We need to handle if we haven’t put any intervals into our output yet and the end of the new interval is less than the start of the current one
2. We need to handle if we have put intervals already into output and the last interval there overlaps with the current one
3. If neither of those cases are true, we want to just append the current variable to our output list

Here’s what this will look like:

We’re not done though. We need one more if statement that will always run after this decision tree.

You see, we’ve handle the cases where the new interval is first and not merged, when an existing interval is present and we merge, and when we just need to push the current_interval to the output list.

However, we separately always need to check if we still need to insert the interval and, if the output list has length, compare the last output interval’s ending to the new_start value of the new_interval.

Let’s add that:

Ugh. I know that was a lot to take in.

Essentially, all this last if statement is doing is merging the new_interval with an existing interval if they overlap. That’s it. It’s just a lot of code.

Before returning our output, we should add the new_interval to the end of output if we never ended up inserting/merging it in the for loop.

Finally, we just return the output list.

This whole thing will run in O(n) time complexity and O(n) space complexity (due to the new output list).

Conclusion

Good job. You made it. What did you think? Was it easier or harder to understand than you expected?

Keep an eye out for the rest of these Blind 75 coding challenges articles I’m doing. It’s going to be a fun ride.

Feel free to reach out (using the links below) if you want to talk about coding, cool tech, or anything else (I really like book recommendations).

Thanks for reading. 🔥

Nathan

(GitHub, LinkedIn, Twitter, and Personal Site)