Ace Your Coding Interview — Blind 75 Solved and Explained — Part 3 Intervals

6 min readJun 11, 2022

This week we are moving on to the third part of our solutions, intervals. Unlike the previous section, these questions are not as loaded and don’t come with as many patterns to learn. There are important techniques used in all the questions below that are crucial to setting up the problem before attempting the solution.

As always the link to the whole Blind 75 is listed below:

New Year Gift - Curated List of Top 75 LeetCode Questions to Save Your Time

New Year Gift to every fellow time-constrained engineer out there looking for a job, here's a list of the best LeetCode…

www.teamblind.com

A topic of big struggle during this topic is the speed and time complexity. There are many ways to solve these problems that allow for more efficient and faster solutions. However, I often find that these optimal approaches are harder to explain and get your head around. Recruiters would rather have a solid explanation of your solution and your thinking process, rather than code that you just memorized and have no idea how it functions.

Question 1: Insert Interval

Insert Interval - LeetCode

leetcode.com

Insertion of the interval requires a bit more attention than just inserting the interval, we also need to update our intervals with overlapping ones so we can display the most concise list. To do this we are going to copy the list onto a new one until we find an overlap, fix the overlap, then finish copying.

Our Approach:

Handle the edge case when the interval is empty. If the new interval array is not empty add the contents of the new interval array to the result array and return the result in the format of an array.
Next, we are going to start copying the contents of the intervals array onto our result as long as it doesn’t include our result. We are going to do this by comparing our first new interval value with the 2nd index of current interval values until they are smaller than the new interval value.
Next, we are going to compare the 2nd index of the new interval with the 1st indexes of the current intervals until we find a 2nd index smaller than the 1st index.
While the last step occurs we are going to need to create a new interval that will be added to our result that encompasses both the new interval and current interval list. For the 1st index of the new interval, we are going to select the minimum value between the first indexes of new and existing intervals, and for the 2nd index, we are going to select the maximum between the second indexes.
Next, we are going to add our new interval that has an insertion included in our list.
Finally, we need to copy all the remaining indexes to our result and return our result in the form of an array.

Question 2: Merge Interval

Merge Intervals - LeetCode

leetcode.com

For this question, we are trying to merge intervals to come up with the least amount of intervals including our new insertion. To do this we need to find where overlaps occur and fit our new interval into those points. We need to keep track of what is happened previously, so we can keep track of the merged intervals.

Our Approach:

Let’s account for the edge case where nothing exists. Return an empty 2d array.
We want to sort our array by the first interval. This is going to be useful when finding overlaps of arrays between each other. We also need to track the previous element. To start off we are going to set our previous to the first element of our array.
Since we already set the first element as our previous pointer. We can start our loop on the second element.
We are going to see if our current interval overlaps with the previous one and if that is the case we are going to merge them. To do this we check if the first index of the current element is greater than the second index of the previous element. If the first index is greater that means the two don’t need to be merged. Therefore, we just add the previous element to our list and update the previous pointer to our current element.
In the case where the elements overlap, we need to update what the previous element looks like to encompass the upcoming element. To do this we take the maximum between the second index between the current and previous interval.
Once we are done looping through the elements we need to add the last element into the result which would just be the previous element itself.
Finally, convert to array and return.

Question 3: Non-Overlapping Intervals

Non-overlapping Intervals - LeetCode

leetcode.com

A Solution to Non-Overlapping Intervals.

Now that we have seen how to check to overlap and merge them we can perhaps use similar skills to solve questions to erase overlapping intervals. In this instance, however, we need to return the number of erased intervals instead of returning a list where the intervals are deleted.

Our Approach:

As per before, let’s account for the edge case where nothing exists. Return a 0.
We want to sort our array by the first interval. This is going to be useful when finding overlaps of arrays between each other. We also need to track the count. We also need an end variable to track the 2nd index of our previous variable. Like before we are going to set this to the first element’s second element.
Since we already have the end variable to be correlated with the first element’s second index we can start our iteration at the 2nd index of our intervals.
We are going to check if our current element has a greater or equal first element to our end variable. If this is found to be true, update the end variable itself and move on with the loop.
Else, we know there are overlapping intervals so we increment the count. With this we are also going to set up a new end variable, we are going to set it as the minimum value between the current end and the 2nd index of the current element.
Finally, by the end of our loop, we will be able to return the count of non-overlapping elements.