[Solution]Problem 53:Merge Overlapping Intervals[Snapchat]

Keep at it my hard working reader. We're about to do amazing things together.

To learn more about the newsletter, check our detailed About Page + FAQs

To help me understand you better, please fill out this anonymous, 2-min survey. If you liked this post, make sure you hit the heart icon in this email.

Recommend this publication to Substack over here

---

How is it going my favorite person on the internet,

I love that you show up regularly to nerd it out with me. I’ve been going over the usage stats and some of you madlads have opened my emails 50 times in the last week. Y’all are reading every email, and clicking the links to read the older ones I link/mention. I have no words. Keep showing up consistently, and you’ll be demons in no time.

This engagement and support push me to keep things going and produce the highest quality content for you. Let’s ride this momentum, all the way to the top.

Problem

This problem was asked by Snapchat.

Given a list of possibly overlapping intervals, return a new list of intervals where all overlapping intervals have been merged.

The input list is not necessarily ordered in any way.

For example, given [(1, 3), (5, 8), (4, 10), (20, 25)], you should return [(1, 3), (4, 10), (20, 25)].

Step 1: Defining the terminology

The first step is always to try and clarify what the terms used in the question are. During your interviews, this is where clarifying questions play a huge role. Always clarify what words/phrases mean, even when they seem obvious. It is a mistake that too many people, especially those that spend a lot of time on Leetcode/Competitive Programming without Mock Interviewing make. By not asking the questions, you’re not letting yourself show off your amazing collaboration and communication skills. These are very important, especially for you mid-level/senior engineers.

In this question, the question would be what do overlapping intervals mean and how do we merge them? The example given is fairly straightforward. Here, one interval is a strict subset of the other. What if the interval was (5,15) instead of (5,8)? How should we proceed then? Mesh them into one, or keep the overlapping parts as 1 interval and non-overlapping as another? This answer to this question might seem ‘obvious’ to some of you, but not asking is really shooting yourself in the foot. If your interviewer wants something different than what you wanted, you’ve hurt your chances. If you had the right idea, then you show the interviewer your ability to step back, consider alternatives, and ask questions. Very attractive quality.

Getting back to defining the phrase, I’m going to go with the standard math definition of merging two intervals (which are basically sets). Simply put, if two intervals have any values in common, we will say they overlap and we will combine the two intervals. In other words, if the intersection of two sets is non-empty, we will take the union of both sets. If nothing else, this will impress your interviewer. It might seem like taking brownie points (it is), but you should take every advantage you get.

Fancy Math Terminology aside, how would we logic code this up? Sure you can use the libraries, but those would be expensive. Turns out this will be simpler than you would think-

Step 2: Coding the Merging Logic

This is a major part of the problem, and our approach will naturally lead us here. Once we can fix this, the rest of our problem will become that much easier.

Let’s take 2 intervals- [s1, e1] and [s2,e2]. How do we know if they overlap and should merge. Remember the set of interval will be all the values b/w s1 and e1. Same for interval 2. If s1<=s2<=e1 (or s2<=s1<=e2, depending on which starting value is bigger) then we know that the sets will have common values, and we should merge them. What would merging be?

Since we know that s2 in contained in the range, we can discard it. The end point of our merged interval will be the greater of e2 and e1. Similarly, the start of our interval will be the lower of the 2 values.

That simple.

Now let’s get to integrating these insights back to the question.

Step 3: Reading the Question Very Carefully

When given questions, I always suggest going through the questions extremely carefully. Really pay attention to the wording, test cases given, and possible DSA being hinted at. This question is a prime example of why that is important. Paying attention to the word/phrase used here can really make solving this problem much easier. Notice the particular phrase-

The input list is not necessarily ordered in any way.

Why would they go ahead to say this? Can ordering make this problem easier to solve? One thing we’ve already noticed is that the starting values of the intervals matter a lot when comparing. But is that all?

Notice that because we compare intervals pairwise, the order in which we look at intervals matters a lot. If we had the example [[2,3],[4,5],[1,6]] we know we should get [1,6]. But if we applied our logic to it, we will get [[2,3],[1,6]].

We can overcome this by doing a bubble-sort-like pairwise comparison of every interval, but this would be very expensive. Since we know that the starting number is what determines interval overlap, we can just sort by that go through. This way we know adjacent (and possibly overlapping) intervals are always compared and merged. We will do that

Step 4: Coding It Up

Now that we got the solution sorted out, let’s get to coding it up.

def merge(intervals):
    result = []
    for start, end in sorted(intervals, key=lambda i: i[0]):
        # If current interval overlaps with the previous one, combine them
        if result and start <= result[-1][1]:
            prev_start, prev_end = result[-1]
            result[-1] = (prev_start, max(end, prev_end))
        else:
            result.append((start, end))
    return result
    
i=[(1, 3), (5, 15), (4, 10), (20, 25)]
print(merge(i))

To non-Python (or those of you not familiar with Lambda Functions in Functional Programming), the for loop might look a little strange. All it does is sorts intervals using on the starting value. To understand the structure (and learn more about Functional Programming)- make sure you go through my posts on the topic. I’ve covered this a while ago, but Functional Programming is a cheat code to getting good at recursion and recursive coding. Don’t overlook it. Search through our archives and take your recursion to the next level.

Time Complexity- O(N*log(N))

Space Complexity- O(M), M being the overlapping intervals. Worst Case is M==N

Loved the solution? Hate it? Want to talk to me about your crypto portfolio? Get my predictions on the UCL or MMA PPVs? Want an in-depth analysis of the best chocolate milk brands? Reach out to me by replying to this email, in the comments, or using the links below.

Stay Woke. I’ll see you living the dream.

Go kill all,

Devansh <3

Reach out to me on:

Instagram: https://www.instagram.com/iseethings404/

Message me on Twitter: https://twitter.com/Machine01776819

My LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/

My content:

Read my articles: https://rb.gy/zn1aiu

My YouTube: https://rb.gy/88iwdd

Get a free stock on Robinhood. No risk to you, so not using the link is losing free money: https://join.robinhood.com/fnud75