Insert Interval Solution for Google
Company: Google · Difficulty: Medium · Topics: Array, Sorting
Problem Statement
You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.
Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).
Return intervals after the insertion.
Examples
Example 1:
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
Explanation:
The new interval [2,5] overlaps with [1,3], so we merge them into [1,5].
Example 2:
Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation:
The new interval [4,8] overlaps with [3,5], [6,7], and [8,10], so we merge them into [3,10].
Example 3:
Input: intervals = [], newInterval = [5,7]
Output: [[5,7]]
Explanation:
Since intervals is empty, we just insert the new interval.
Intuition
The key insight is that we need to handle three cases:
1. Intervals that come before the new interval (no overlap)
2. Intervals that overlap with the new interval (need to merge)
3. Intervals that come after the new interval (no overlap)
We can process the intervals in order and merge overlapping ones as we go.
Approach
1. Initialize an empty result array
2. Add all intervals that end before the new interval starts (no overlap)
3. Merge all overlapping intervals with the new interval
4. Add all intervals that start after the new interval ends (no overlap)
5. Return the result
Solution
⚠️ Disclaimer: Don't jump directly to the solution, try it out yourself first. Only look at the solution after you've given it a good attempt.
Solution: Linear Scan Approach
Time Complexity: O(n) - Single pass through the array
Space Complexity: O(n) - Space for the result array