MediumNeetCode150Array
Insert Interval
Insert new interval and merge.
Examples
Input
intervals = [[1,3],[6,9]], newInterval = [2,5]
Output
[[1,5],[6,9]]
Merged [1,3] and [2,5].
Constraints
- •
0 <= intervals.length <= 10^4 - •
intervals[i].length == 2 - •
newInterval.length == 2
Approaches
Append and merge.
CodeT: O(n log n) | S: O(n) output space
Before, overlap, after.
CodeT: O(n) | S: O(n) output space
Same approach.
CodeT: O(n) | S: O(n)
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Append + Sort | O(n log n) | O(n) output space | Append and merge. |
| Three-Phase Linear | O(n) | O(n) output space | Before, overlap, after. |
| Three-Phase Optimized | O(n) | O(n) | Same approach. |
Append + Sort
T: O(n log n)S: O(n) output space
Append and merge.
Three-Phase Linear
T: O(n)S: O(n) output space
Before, overlap, after.
Three-Phase Optimized
T: O(n)S: O(n)
Same approach.
Common Mistakes
Not handling empty intervals
Wrong merge condition
Off-by-one