Merge Intervals
LeetCode 56 • Medium • Intervals
Given an array of intervals where intervals[i] = [start, end], merge all overlapping intervals and return the non-overlapping intervals.
TimeO(n log n)sort + linear scan
SpaceO(n)result list
Index: —
Current: —
Result: —
Ready
Press Play. Sort by start, then scan: if next start ≤ current end, merge; else add new interval.
TimeO(n log n)sort + linear recurse
SpaceO(n)result + call stack
Recursive: helper(i, current) — base when i ≥ n return [current]; if overlap merge and recurse; else return [current] + helper(i+1, next).
Practice until you don't need to look. Use the guide comments below as scaffolding. The green highlights are the nuances to burn into memory.
PATTERN ▸ Sort by start, merge when next_start ≤ curr_end O(n log n) · O(1)
① BASE
if len(intervals) <= 1: return intervals
② SORT
intervals.sort(key=lambda x: x[0])
③ BUILD RESULT
result = [intervals[0]]
for i in range(1, len(intervals)):
curr_end = result[-1][1]
if intervals[i][0] <= curr_end: merge
else: result.append(intervals[i])
④ RETURN
return result
▼ your implementation ▼
Verify your solution: