All patterns
Sorting
Pay O(n log n) once to make later steps linear or logarithmic.
time O(n log n)space O(1) to O(n)
What it is
Sorting exposes structure: equal items become adjacent, pairs can be found with two pointers, intervals can be merged in a single pass. It is often the cheapest way to remove an O(n²) search.
When to reach for it
- Intervals, meeting rooms, merging
- Duplicates or closest pairs
- Greedy choices by order
Clues in the problem
- Order of the original input does not matter
- Comparisons between neighbours are enough
Template
def merge_intervals(iv):iv.sort(key=lambda p: p[0])out = [iv[0]]for s, e in iv[1:]:if s <= out[-1][1]:out[-1][1] = max(out[-1][1], e)else:out.append([s, e])return out
Practice problems
- Merge Intervals
- Meeting Rooms II
- 3Sum
- Non-overlapping Intervals
Common mistakes
- Losing original indices
- Sorting inside a loop
- Assuming sort is stable when the language does not guarantee it