Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Insert Interval

LeetCode #57Medium
Sorted list · three-phase sweep · no sort

Given a sorted list of non-overlapping intervals and a new interval, insert it and merge any overlaps, returning the still-sorted, non-overlapping result.

Asked atAmazonGoogleLinkedIn
step 1 / 5
[1,3]
[6,8]
new [2,4]
0
1
2
3
4
5
6
7
8
[0][1][2][3][4][5][6][7][8]
Three-phase sweep
▸
1out ← []; i ← 0
2// phase 1: intervals entirely before new
3while i < n and intervals[i].end < new.start:
4    out.append(intervals[i]); i++
5// phase 2: merge every overlapping interval into new
6    while i < n and intervals[i].start <= new.end:
7        new = [min(starts), max(ends)]; i++
8out.append(new)
9// phase 3: copy the rest
10while i < n: out.append(intervals[i]); i++
11return out
state
  • intervals[1,3] [6,8]
  • new[2,4]
  • out[]

line 1The list [1,3] [6,8] is already SORTED and non-overlapping, so we never sort — one left-to-right pass is O(n). The new interval [2,4] (gold) gets slotted in, merging with anything it touches. We sweep in three phases: before, overlapping, after.