-
Notifications
You must be signed in to change notification settings - Fork 0
160 — Insert Interval
LeetCode 57 · Medium. You're given an array of non-overlapping intervals intervals sorted by start time, and a new interval newInterval. Insert newInterval into intervals so the result is still sorted by start time and still has no overlapping intervals (merging where necessary), and return it.
Picture a shelf of sorted, non-overlapping appointment cards, and someone hands you one more card to slide in. Most of the shelf doesn't care at all — the cards that end well before your new card starts stay exactly where they are, and the cards that start well after your new card ends also stay exactly where they are. The only work happens in the narrow middle stretch: any card whose time range touches or crosses the new one gets absorbed into it, stretching the new card's own start and end to cover everything it collides with. Once nothing left in the pile overlaps it, you drop the (possibly now-bigger) new card into that gap and you're done — no need to touch the rest of the shelf, and no need to re-sort anything, because it was already sorted going in.
"Insert a new interval into an already-sorted, non-overlapping list" is the tell that separates this from generic Merge Intervals: the existing array is a solved problem already (sorted, no overlaps), so you don't need to sort or re-scan the whole thing — you only need one linear pass split into three phases relative to where the new interval lands.
Ignore that intervals is already sorted and non-overlapping — just throw newInterval into the pile and run the general "sort everything, then merge overlapping runs" algorithm from scratch.
func insertBruteForce(_ intervals: [[Int]], _ newInterval: [Int]) -> [[Int]] {
var all = intervals
all.append(newInterval)
all.sort { $0[0] < $1[0] }
guard !all.isEmpty else { return [] }
var result: [[Int]] = [all[0]]
for interval in all.dropFirst() {
let lastIndex = result.count - 1
if interval[0] <= result[lastIndex][1] {
result[lastIndex][1] = max(result[lastIndex][1], interval[1])
} else {
result.append(interval)
}
}
return result
}
// smoke test
print(insertBruteForce([[1,3],[6,9]], [2,5]))
// [[1,5],[6,9]]
print(insertBruteForce([[1,2],[3,5],[6,7],[8,10],[12,16]], [4,8]))
// [[1,2],[3,10],[12,16]]
print(insertBruteForce([], [5,7]))
// [[5,7]]
print(insertBruteForce([[3,5],[6,9]], [1,2]))
// [[1,2],[3,5],[6,9]]Big-O: O(n log n) time — dominated by re-sorting all n + 1 intervals even though n of them were already in sorted order. O(n) space for the merged result.
Walk intervals once, left to right, in three phases relative to newInterval: intervals that end before it starts get copied through untouched, intervals that overlap it get folded into it (growing its start/end boundaries), and once nothing overlaps anymore, the (possibly grown) new interval is appended followed by everything still left over.
func insert(_ intervals: [[Int]], _ newInterval: [Int]) -> [[Int]] {
var result: [[Int]] = []
var i = 0
let n = intervals.count
var newStart = newInterval[0]
var newEnd = newInterval[1]
// Phase 1: intervals that end strictly before newInterval starts — no overlap possible.
while i < n && intervals[i][1] < newStart {
result.append(intervals[i])
i += 1
}
// Phase 2: intervals that overlap (or touch) newInterval — absorb them all.
while i < n && intervals[i][0] <= newEnd {
newStart = min(newStart, intervals[i][0])
newEnd = max(newEnd, intervals[i][1])
i += 1
}
result.append([newStart, newEnd])
// Phase 3: everything left starts strictly after the (grown) new interval ends.
while i < n {
result.append(intervals[i])
i += 1
}
return result
}
// smoke test — same cases as the brute force
print(insert([[1,3],[6,9]], [2,5]))
// [[1,5],[6,9]]
print(insert([[1,2],[3,5],[6,7],[8,10],[12,16]], [4,8]))
// [[1,2],[3,10],[12,16]]
print(insert([], [5,7]))
// [[5,7]]
print(insert([[3,5],[6,9]], [1,2]))
// [[1,2],[3,5],[6,9]]Big-O: O(n) time — a single linear pass, since intervals arrives already sorted. O(n) space for the result array.
The brute force throws away the one fact that makes this problem easier than general Merge Intervals: intervals is already sorted and already non-overlapping. Re-sorting the whole thing after tossing in one more element wastes the ordering you were handed for free. Because everything is sorted, newInterval can only possibly overlap a contiguous run of the array — never a scattered set of far-apart intervals — so a single linear scan can cleanly separate "before," "overlapping," and "after" without ever needing to look at an element twice or compare against anything out of order.
- Merge Intervals — this is that same pattern's own recognition signal calling out this exact variant: "splicing one new range into an already-sorted one, merging only where the new range collides."
-
Arrays and Strings — both versions scan a plain backing array of
[start, end]pairs and build the answer into a second array as they go.
Insert Interval is three phases in one pass — copy what's before, absorb what overlaps, copy what's after.
- Why does Phase 1's stopping condition use
intervals[i][1] < newStart(strictly less than), while Phase 2's stopping condition usesintervals[i][0] <= newEnd(less than or equal)? What would break if Phase 2 used strict<instead? - Trace
insert([[1,2],[3,5],[6,7],[8,10],[12,16]], [4,8])by hand. Which intervals get absorbed in Phase 2, and what arenewStart/newEndafter each one? - Why doesn't this algorithm ever need to sort anything, when the near-identical Merge Intervals problem does?
- What happens if
newIntervaldoesn't overlap any existing interval — say it belongs at the very front or very back? Walk through why Phase 2 still behaves correctly (inserting it with zero absorptions).
⬅️ Previous: Valid Parenthesis String · Next: Merge Intervals ➡️