57 — Insert Interval

Problem Statement

Restating Info We’re Already Given:

• Non-overlapping integer list intervals that is sorted by start time ascending
• For each interval, start time ≤ end time
• Return intervals after inserting newInterval, maintaining ascending order sort

Questions/Clarifications to Possibly Ask Interviewer (If starting information we’re given isn’t sufficient to begin):

• Do we have any space constraints?
• Can we begin with any assumptions for intervals? (In this case we can, but in real life != leetcode problem)
• Are the intervals properly formatted? (In this case yes, but again in real life != leetcode problem)

Discuss Naive Solution:

We can insert newInterval to the end of intervals, sort intervals in ascending order (using a lambda function) and append each interval to a result list. The sorting will dominate the runtime complexity and make it O(n log n).

O(n log n) runtime complexity, O(n) space complexity

Discuss Alternative Solution:

We can improve the insertion of newInterval. To do so, we use the fact that invervals is sorted in ascending order of startTime(s). Thus, we compare these startTime(s) with newInterval’s startTime. This reduces the runtime complexity to O(n).

O(n) runtime complexity, O(n) space complexity

Discuss Optimal Solution:

Another improvement can be made; we can solve this without creating a new result array — we can use the intervals list. We have 2 pointers to keep track of the most previous interval and the current interval we’re comparing. Upon interval overlap, i.e. when we change the previous interval’s end time, we delete the current interval as it’s being combined with the previous interval. Otherwise, there’s no overlap and we move our pointers.

Code Optimal Solution:

https://leetcode.com/submissions/detail/682516007/

Runtime/Space Complexity:

In our first pass through intervals, we look for the correct place to insert newInterval. After inserting newInterval, we consolidate intervals on our second pass. We can do that in place by keeping track of the previous interval and the current interval.

We create 2 integer variables, so a constant amount of space is used.

Test Cases:

• One where newInterval’s correct insertion index is 0
• One where newInterval’s correct insertion index is n-1 for length n intervals list
• One where the result is length 1 (each interval in interval and newIntervals was combined into 1 final interval)
• One where combining multiple different intervals is needed
• One with no interval combining