[Top Interview 150] 57. Insert Interval

Solution)

 

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        res = []

        for i in range(len(intervals)):
            # when newInterval is less than cur interval
            # and don't overlap
            if newInterval[1] < intervals[i][0]:
                res.append(newInterval)
                return res + intervals[i:]

            # when newInterval is greater than cur interval
            # and don't overlap
            elif newInterval[0] > intervals[i][1]:
                res.append(intervals[i])

            # update newInterval when the two intervals overlap
            else:
                newInterval = [min(newInterval[0], intervals[i][0]), max(newInterval[1], intervals[i][1])]
        
        res.append(newInterval)
        return res

 
 
Problem: LeetCode
Reference: NeetCode
 
Time Complexity: O(n)
Space Complexity: O(n)
 
 

Explanation)

 
There are 3 situations that can be reached.
 

1. newInterval is located before an interval and they don't overlap
2. newInterval is located after an interval and they don't overlap
3. newInterval and an interval overlap

Our ultimate goal is to either reach condition 1 or 2. Condition 3 is merely a step to udpate newInterval. 
 
 

Initialization)
 

Instead of modifying intervals in-place, we'll have a list variable res that will save proper intervals.
 

def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        res = []

 
 

When newInterval is placed before the current interval)
 

If we find that newInterval is less than the current interval and they don't overlap, what should we do?
 
We put newInterval first, then we add the rest of the intervals in order.
 

def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        res = []

        for i in range(len(intervals)):
            if newInterval[1] < intervals[i][0]:
                res.append(newInterval)
                return res + intervals[i:]

 
 

When newInterval is placed after the current interval)

 
If newInterval is greater than the current interval and they don't overlap, what should we do?
 
Unlike the previous condition, we only can append the current interval to res. You might think that we can

1. Append the current interval
2. Append newInterval 
3. Append the rest of intervals

However, we do not know if newInterval and the rest of intervals overlap or not. Thus, we cannot do nothing other than appending the current interval for now.
 

def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        res = []

        for i in range(len(intervals)):
            if newInterval[1] < intervals[i][0]:
                res.append(newInterval)
                return res + intervals[i:]

            elif newInterval[0] > intervals[i][1]:
                res.append(intervals[i])

 

When newInterval and the current interval overlap)
 

What should we do if newInterval and the current interval overlap?
 
Obviously, we need to merge those two intervals. The tricky part is where to save it and how to use that information.
 
NeetCode saves the merged interval to newInterval. The reason why we save the merged interval to newInterval is because we need to compare newInterval with future intervals as written in the conditions. 
 
Since we don't know if this new merged interval might overlap again with future intervals, thus we don't add newInterval until we're done with the iteration (we don't add newInterval until we're sure that newInterval doesn't affect the rest of the intervals). Think of this step as updating newInterval to eventually reach either the 1st or 2nd condition.
 
Once the iteration is over, we now have the most recently updated newInterval. So we append newInterval to res and return res.
 

def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        res = []

        for i in range(len(intervals)):
            if newInterval[1] < intervals[i][0]:
                res.append(newInterval)
                return res + intervals[i:]

            elif newInterval[0] > intervals[i][1]:
                res.append(intervals[i])

            else:
                newInterval = [min(newInterval[0], intervals[i][0]), max(newInterval[1], intervals[i][1])]
        
        res.append(newInterval)
        return res

 
 
 
I had all these logics in my head, but I didn't know how to weave all of them together to make them work with each other. This solution is honestly out of my range, and I'm not even sure if I can come up with it by myself. What a clever/concise solution.