Custom Comparators
What is this?
Sometimes "smallest to largest" isn't the order you want. A comparator is a little rule you hand the sort that, for any two items, says which one comes first. With the right rule you can order by frequency, by a made-up alphabet, or by which pairing forms the biggest number — and the sort handles the rest.
💡 Fun fact: Telling a sort what to compare instead of writing the sort yourself is why one well-chosen comparator can turn a hard interview problem into a single line of code.
🔓 The 4 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
Core idea: Sorting isn't only "smallest to largest." When the right order is some other rule — biggest concatenation, highest frequency, a made-up alphabet — you hand the sort a custom comparator (or a custom key) that says, for any two items, which comes first. Get that pairwise rule right and the library sort does the rest in O(n log n).
The pattern
A comparator answers one question: given items a and b, which goes first? The trick is choosing the comparison that makes the global arrangement come out right. Sometimes the key is a transformed value (frequency, then value as a tie-break). Sometimes it's a direct pairwise test — comparing
a+bagainstb+ainstead of the numbers themselves. When the ordering is by count, you often skip the comparator entirely and bucket by count, reading buckets back in the order you want. And to verify an order rather than produce one, replace each element by its rank in the target order and check the sequence is non-decreasing.
The problems
- Largest Number — sort the numbers as strings with the pairwise rule "a before b if
a+b>b+a"; concatenate the result. The clever comparator sidesteps a tricky greedy argument. - Sort Array by Increasing Frequency — count occurrences, then sort by frequency ascending, breaking ties by value descending. A two-key comparator.
- Sort Characters By Frequency — tally each character, then bucket by count and emit characters from high-count buckets to low; build the output string.
- Verifying an Alien Dictionary — build a rank map from the alien alphabet, then check each adjacent word pair is in order under that ranking (with the prefix edge case).
Key takeaways
- A comparator is just a pairwise "who's first?" rule — pick the one that makes the whole order correct.
- Multi-key sorting chains tie-breakers (frequency, then value) into one comparator.
- Bucket by count when the order is purely by frequency — often beating a comparator outright.
- To verify an order, map to ranks and check the sequence is monotonic.
- Why it matters: real data rarely sorts by its raw value — custom orderings are the everyday tool.
Order: Largest Number → Sort Array by Increasing Frequency → Sort Characters By Frequency → Verifying an Alien Dictionary.
Sort Array by Increasing Frequency
Core idea: You want one ordering that obeys two rules at once — rarer values come first, and among equally-rare values the bigger number comes first. Don't write a hand-rolled comparator or sort in two confusing passes. Count the frequencies once with a
Counter, then sort with a tuple key(freq[x], -x). Python compares tuples left-to-right, so it sorts by frequency ascending, and-xflips the value tie-break into descending — all in one stableO(n log n)sort.
The problem, rephrased
Imagine you run a music app and you've got a list of the song IDs that played during one shift, in scan order. You want to build an "underplayed first" rotation: songs that were played least should appear at the front so they get a chance, and the most-played songs sink to the back. But there's a tie-break rule — when two songs were played the same number of times, the one with the higher ID goes first (say, higher IDs are newer releases you want to surface). Produce the full reordered playlist (every play kept, just reordered).
Strip the story away and it's LeetCode 1636 — Sort Array by Increasing Frequency: given an integer array nums, sort it so values appear in increasing order of how often they occur; if two values occur equally often, place them in decreasing order of value. Return the sorted array.
| Input | Frequencies | Output | Why |
|---|---|---|---|
nums = [1,1,2,2,2,3] |
3→1, 1→2, 2→3 |
[3,1,1,2,2,2] |
3 (freq 1) < 1 (freq 2) < 2 (freq 3) |
nums = [2,3,1,3,2] |
1→1, 2→2, 3→2 |
[1,3,3,2,2] |
1 is rarest; 2 and 3 tie at freq 2 → bigger first → 3 block before 2 block |
nums = [-1,1,-6,4,5,-6,1,4,1] |
5→1, -1→1, 4→2, -6→2, 1→3 |
[5,-1,4,4,-6,-6,1,1,1] |
freq-1 group {5,-1} desc → 5,-1; freq-2 group {4,-6} desc → 4,-6; then freq-3 1 |
Note the output is the same multiset as the input — every element is preserved, only the order changes.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson