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.
Verifying an Alien Dictionary
Core idea: Someone hands you a brand-new alphabet — the same 26 lowercase letters, but reshuffled into a different priority order — and a list of words. You must decide whether the words are sorted under that alphabet. The trick: don't write a clever string comparator. Build a tiny
letter → ranklookup from the custom order, and now every letter is just a number. Comparing two words becomes ordinary lexicographic comparison on those numbers. Walk each adjacent pair once; the only wrinkle is the prefix rule ("app"may come before"apple", never the reverse). One linear pass over all characters, O(total chars).
The problem, rephrased
A library on a distant planet uses the same English lowercase letters we do — but its dictionary files them in a different order. You're given that planet's alphabet as a string order (a permutation of all 26 letters, where the first character is "smallest" and the last is "largest"), plus a list of words. Return True if and only if the words are already sorted in lexicographic order according to order.
"Lexicographic" means dictionary order: compare two words character by character; at the first position where they differ, whichever has the smaller letter (under order) comes first. If one word runs out before any difference appears, the shorter word comes first.
This is LeetCode 953 — Verifying an Alien Dictionary.
| Input | Means | Output |
|---|---|---|
words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz" |
'h' ranks before 'l', so "hello" < "leetcode" |
True |
words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz" |
at index 3, 'd' ranks after 'l', so "word" > "world" |
False |
words = ["app","apple"], order = "abcdefghijklmnopqrstuvwxyz" |
"app" is a prefix of "apple" and is shorter → fine |
True |
The function returns a single boolean.
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