Insert Interval

Medium#57merge

You get a list of intervals sorted by start, with no two overlapping, and one new interval. Put the new interval in, merge it with every interval it overlaps or touches, and return a list that is still sorted and has no overlaps. Our example: [0, 2], [3, 5], [7, 8], [9, 12] and the new [4, 7] — the answer is [0, 2], [3, 8], [9, 12].

57 Insert IntervalWalkthrough · 1×

Example: [0, 2], [3, 5], [7, 8], [9, 12], new [4, 7]. The list is on top, the new interval [lo, hi] below it, then the result.

[0, 2][3, 5][7, 8][9, 12]result0123456789101112
not looked at yetintervals[i]the new interval [lo, hi]already handledresult

The result is empty so far

01/20
restart · back · play · step
Speed
1function insert(intervals, newInterval):
2 result = []
3 [lo, hi] = newInterval
4 i = 0; n = len(intervals)
5 while i < n and intervals[i].end < lo:
6 add intervals[i] to result; i = i + 1
7 while i < n and intervals[i].start <= hi:
8 lo = min(lo, intervals[i].start)
9 hi = max(hi, intervals[i].end)
10 i = i + 1
11 add [lo, hi] to result
12 while i < n:
13 add intervals[i] to result; i = i + 1
14 return result
state
result
[]
lo
–
hi
–
i
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. The list is sorted and has no overlaps, so it splits into three runs in a row: intervals that end before lo, intervals that overlap the new one, and intervals that start after it. No sort is needed.
  2. Every overlapping interval widens [lo, hi] with min of the starts and max of the ends. One merged interval replaces them all, so the result has no overlaps.
  3. Touching counts as overlapping, and the signs say so: end < lo leaves an interval out only if it ends before lo, and start ≤ hi lets [7, 8] in, though it only starts at hi = 7.

Complexity

Time O(n): each interval is looked at once across the three loops. Memory O(n) for the result.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.