Merge Intervals (LeetCode #56)

Image by Chris Linnett 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 Longest Common Subsequence.

Introduction

If you’re looking for a quick walkthrough of an optimal solution to the LeetCode Merge Intervals 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 intervals where each interval has a list structure of [start, end] where start and end are number values
2. We should merge all overlapping intervals (e.g. [[3, 5], [4, 6]] should turn into [[3, 6]])
3. We should return a list of non-overlapping, merged intervals that cover all the intervals in the input intervals list
4. The length of the intervals list can be 1 <= len(intervals) <= 10^4
5. Each interval in the intervals list is guaranteed to be length 2 (with a [start, end])
6. The values inside each interval will be 0 <= start <= end <= 10^4

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.

With all of that being said, let’s get to it!

Let’s Get Setup 🏗

The first thing we want to do is to get an output list setup (for our final answer of merged intervals) and also sort the intervals list. It didn’t mention it was sorted in the problem introduction, but it also didn’t disallow us sorting it ourselves.

This is what this will look like in code form:

Don’t worry too much about that getSortVal function. It’s just the way Python handles deciding how to sort values in a list like each of our intervals of [start, end] (where the values might be something like [3, 10]. We’re going to sort on the first value at index 0.

Okay. Believe it or not, we’re setup for our pass through all the intervals in intervals. Let’s go ahead and get into our loops!

Building Our Loops 🔁

The first thing we need to do is iterate over each interval in intervals and pull out the current start and current end of each of them:

After this, we need to check if we’ve previously added anything to our output list. If we haven’t, there’s nothing to overlap with yet — right?

In that case, we’ll just add it to the output list:

If we have added values to the output list already, we need to pull out the last value in the output list and compare it against the current interval values we already have:

Whoa. That’s a lot.

Okay, I’m about to teach you the key to most “interval” type of problems. It’s not strictly speaking necessary for this problem (you could just compare the end of the last interval to the start of the next one). But I’m including this since it’s a great key for all future interval problems:

1. Create a variable to get the maximum of the prev_start and the current_start
2. Create a variable to get the minimum of the prev_end and the current_end
3. If the resulting max_start is still less than the resulting min_end, the intervals are overlapping

Read that through (along with the code above) as many times as it takes to make it click. It will be well worth your time for future interviews, I promise. Here’s an example to help make it click for me:

intervals = [[1, 3], [2, 5]]
max_start = 2
min_end = 3
max_start <= min_end = True

Okay. Let’s go on.

Now, you might be asking why we also set a variable for max_end. It’s because we need that if we find that we overlapped with our previous interval in output. If that’s the case, we merely want to set the end value of the previous interval already in output to be whatever the max_end is:

If this isn’t the case (in other words, if the intervals aren’t shown to be overlapping), we can merely push the new current non-overlapping interval we’re looking at into our output list:

When we’re all done, we can merely return the output list.

This solution will run in a time complexity of O(n log n) (since we used .sort() which runs Timsort — which is a variation of Merge Sort — under the hood which has this time complexity) and a space complexity of potentially O(n) in the worst case if no intervals are overlapping (where n is the length of intervals).

Conclusion

Great job. I hope this helped you out a lot!

Keep an eye out for the rest of these Blind 75 coding challenges articles. 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)