Custom comparator / key sort

34 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

You have the numbers 3, 30, 34, 5, 9 and must glue them together, in some order, to make the largest possible number. Trying a few: 9534330, 9533430, 3430953. The biggest is 9534330.

By hand you might try every order: 5 numbers give 120 orders, 10 numbers give 3.6 million, 20 numbers give more than a billion billion. You need a way to decide the order without trying them all.

Your first instinct is "sort from biggest to smallest": 34, 30, 9, 5, 3 gives 3430953, which is wrong, because 9 should come first. Second instinct: "sort by the first digit": then 3, 30 and 34 all tie, and ordinary comparison says 30 < 34 < 3 or similar, but 3 should go before 30 (330 beats 303) and after 34 (343 beats 334). The usual order of numbers is the wrong order for this problem.

Build the structure, one piece at a time

Sorting is the structure, but with a custom rule for "which of two things comes first".

Piece 1: a rule for two items. Given a and b, glue them both ways as strings and compare: a goes before b if a+b is bigger than b+a. For 3 and 30: "330" versus "303", so 3 first. For 3 and 34: "334" versus "343", so 34 first. For 5 and 9: "59" versus "95", so 9 first.

Piece 2: hand the rule to a sort. Any sorting algorithm only ever asks "does a come before b?" Give it this rule and it produces 9, 5, 34, 3, 30.

Piece 3: glue the result. "9" + "5" + "34" + "3" + "30" = 9534330. Strip leading zeros if everything was 0.

Many problems only need the simpler form of this idea: a key for each item (its frequency, its distance from the origin, its length) and the sort orders by the key. The pairwise rule is for when no single number per item captures the order, as here.

Why it is correct

A sort is only meaningful when the rule is a total order: it must be consistent, so that if a comes before b and b before c, then a comes before c. Otherwise different sorting algorithms could give different results, or loop.

For the gluing rule, consistency holds, and the reason is a small piece of algebra. Writing a+b as a number means a × 10^len(b) + b. So "a+b > b+a" is

a × 10^len(b) + b > b × 10^len(a) + a, which rearranges to a / (10^len(a) − 1) > b / (10^len(b) − 1)

So the rule compares each number by the single value a / (10^len(a) − 1), which is the value of the infinite repetition 0.aaa… Comparing by a single value is always consistent. That also explains the answer: 9 = 0.999… beats 5 = 0.555… beats 34 = 0.3434… beats 3 = 0.333… beats 30 = 0.3030….

Why is the sorted order the best? If two adjacent numbers in the final string were in the wrong order, swapping them would make the string bigger (only those digits change, and the rule says the swap wins), so the best string has every adjacent pair in rule order, which is exactly what the sort produces.

Why it is fast

A comparison sort makes about n log₂ n comparisons, and each comparison here concatenates two short strings.

time = O(n log n × L) for numbers of up to L digits

For 20 numbers that is around 90 comparisons instead of a billion billion orders.

How to recognise it in an interview

The cues are "arrange to form the largest/smallest", "sort by frequency then by value", "closest k points", "relative order given by another array", or any "order these by a rule" wording. Ask yourself whether one key per item captures the order; if not, whether a pairwise rule is consistent. Say: "I define the comparison for two items, check it is a total order, and sort once."

Largest Number is the example above. Sort Characters By Frequency sorts letters by a key, their count, descending. K Closest Points to Origin sorts by the key x² + y² and takes the first k (a heap or quickselect can avoid the full sort).

02The idea in one line

Define 'better' pairwise or as a key, then sort once.

Reach for it when: Largest number, sort by frequency, relative sort, k closest points.

Cost: O(n log n) time.

03The walk-through, step by step

The video works one example: Largest Number on [3,30,34,5,9]. These are its captions in order, so you can follow without the video or check a step you missed.

1. Define a before b iff the string a+b > b+a, then sort once
2. Compare 3 and 30: 330 vs 303 → 3 goes first
3. Compare 3 and 34: 334 vs 343 → 34 goes first
4. Compare 5 and 9: 59 vs 95 → 9 goes first
5. Compare 30 and 34: 3034 vs 3430 → 34 goes first
6. Sort with that comparator (it is a valid total order)
7. Concatenate: 9534330
8. One sort with a pairwise rule: O(n log n) comparisons

04Asked at Google

8 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Sorting: Cyclic sort (1..n placement), Quickselect (kth element), Merge sort with counting, Bucket / counting sort.