1Understand
The idea
Sorting costs O(n log n) but often exposes structure that makes the rest linear: duplicates become adjacent, the closest values become neighbours, and greedy choices become obvious. When the order itself is the question, a custom key or a comparison that combines two items decides it.
Intuition
Sorting costs O(n log n) but often exposes structure that makes the rest linear: duplicates become adjacent, closest values become neighbours, and greedy choices become obvious once items are ordered.
When the order itself is the question, a custom key (or a comparison that combines fields) decides it. Sorting indices instead of values preserves a way back to the original positions.
Do the sort once up front. Re-sorting inside a loop is a common accidental O(n² log n).
What you will be able to do
- Sort with tuple keys
- Recognise when sorting simplifies the problem
When to use it
- Order does not matter in the output
- Closest / adjacent values
- Rank by several criteria
2See it
Walkthrough
Sort then scan
nums = [3, 1, 2, 1], sorting unlocks adjacent comparisons.
1 / 6
Unsorted. Many problems become easy once equal or consecutive values sit next to each other.
Live template
Line 1 active
Complexity: time O(n log n), space O(n)
O(n log n) time dominates; extra space depends on the sort (Timsort may use O(n)). If the value domain is tiny, counting sort is O(n + U). When you need original indices, sort (value, index) pairs or argsort.
Read the walkthrough as text
Meeting rooms / overlap check after sort. Intervals [[0,30],[5,10],[15,20]].
- Sort by start: already in that order.
- Scan adjacent pairs:
5 < 30→ overlap; you can stop or count conflicts depending on the problem. - For "merge intervals", keep a result list and extend the last end when the next start ≤ current end.
Sorting first turns an O(n²) pairwise check into O(n log n) + O(n).
3Recognise it
Kinds of problems (6)
Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.
Sort then scan adjacent pairs
Example. Contains duplicate, or minimum difference between any two values.
How. Sort once; adjacent elements are the only neighbours worth comparing.
Multi-key custom order
Example. Sort people by height desc, then name asc.
How. Tuple key: sort by (-height, name) so ties break deterministically.
Counting sort for small ranges
Example. Values in 0..100, sort in linear time.
How. count[value]++; emit each value count times, O(n + range).
Largest number / custom comparator
Example. Arrange digits so concatenation is maximal.
How. Sort pairs (a, b) by whether str(a)+str(b) > str(b)+str(a).
Sort indices instead of values
Example. Return ranks or reorder by original positions after sorting scores.
How. Sort range(n) by key=lambda i: nums[i]; values stay put, order of indices changes.
Interleave after sorting (wiggle order)
Example. Reorder so nums[i] < nums[i+1] > nums[i+2] < …
How. Sort, then swap every other pair from index 1 upward.
Common mistakes
Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.
Wrong tie-breaking
Why it happens. Tuple key fields or negation for descending order are flipped.
How it fails. Sort by score descending then name ascending but key uses (score, name), high ties sort names Z→A.
Fix. Match the spec: (-primary, secondary) for high-first primary; test one tie case.
Lost original index
Why it happens. Values are sorted when the answer must refer to original positions.
How it fails. Return index of the two largest after sorting nums, indices no longer match the original array.
Fix. Sort (index, value) pairs, or sort indices by value: sorted(range(n), key=lambda i: nums[i]).
Sorting inside a loop
Why it happens. Re-sorting after each local change wastes time.
How it fails. For each of n removals, re-sort the array, O(n² log n) instead of one O(n log n) sort.
Fix. Sort once up front, or update order with a heap / insertion in the right structure.
4Check yourself
Concept check
A short quiz on this lesson before you practise. Optional, and it does not gate coding.
Ready to practise?
Mastery comes from solving. The lesson is optional context.