FAANG · LeetCode #56

Merge Intervals — three-stage drill

1The ProblemMedium

Merge Intervals

Merge all overlapping intervals and return the non-overlapping set.

Examples

[[1,3],[2,6],[8,14],[9,11],[15,18]]→ [[1,6],[8,14],[15,18]][[1,4],[4,5]]→ [[1,5]]

constraintSort by start first; then a single left-to-right sweep merges in place.

2The PatternTIME O(n log n) · SPACE O(n)

Intervals

Given a pile of ranges, sort them by start — now any overlap is a neighbour, so a single left→right pass handles them.

Problems using this pattern

3The SolutionRESULT → [[1,6],[8,14],[15,18]]

Step through it

the input as given — not yet sorted

Step 1 / 12

Python▎sort · then merge or emit

1def merge(intervals):
2    intervals.sort(key=lambda x: x[0])
3    out = [intervals[0]]
4    for s, e in intervals[1:]:
5        if s <= out[-1][1]:          # overlaps
6            out[-1][1] = max(out[-1][1], e)
7        else:                         # gap
8            out.append([s, e])
9    return out

why it worksSort by start so overlaps can only be adjacent. Sweep left→right keeping one 'running' interval: if the next interval starts at or before the running end, it overlaps — extend the end (merge). Otherwise there's a gap — emit the running interval and start a new one. Sorting dominates: O(n log n).

Arrow keys to navigate · escape to reset

All problems by pattern

Two Pointers

Sliding Window

Prefix Sum

Monotonic Deque

Shortest Subarray with Sum at Least K

Binary Search

Arrays & Hashing

Monotonic Stack

Intervals

Merge Intervals — three-stage drill

Merge Intervals

Intervals

Step through it

All problems by pattern

Two Pointers

Sliding Window

Prefix Sum

Monotonic Deque

Binary Search

Arrays & Hashing

Monotonic Stack

Intervals

Heap / Top-K

Backtracking

Recursive Descent