Sorting digit segments so their concatenation is largest: why is the pairwise rule a+b vs b+a correct?
answer
- look at just two neighbours at a time
- what is before and after them is unchanged
- both arrangements span the same total length
- swap away one inversion at a time
- sorting by a rule demands the rule be transitive
basics
~20 sAn adjacent-swap exchange argument proves it: swapping a neighbouring pair that breaks the rule never shrinks the result, since the surrounding text and the pair's span are unchanged. Sorting by the rule is valid only because it is transitive.
solid answer
~50 sTake any ordering and look at two adjacent segments `a` then `b`. The two candidate results are `P + a + b + S` and `P + b + a + S` with identical `P` and `S`, and the swapped block has the same total length either way, so the whole-string comparison collapses to comparing `a+b` against `b+a` — the surrounding context cancels. That means any ordering containing an adjacent pair in the wrong order can be swapped without losing value, and each such swap removes one inversion, so finitely many swaps carry any ordering to the rule-sorted one without ever decreasing the result. Hence the sorted order is maximal. The hidden obligation is transitivity: sorting by a pairwise rule is only well defined if the rule induces a consistent total order. This one does; a non-transitive rule would make 'sorted' depend on the sorting procedure.
go deeper
Recall that comparing two segments by value or length is wrong, and that the rule asks which of the two possible arrangements of that pair reads larger. Try it on a short and a long segment sharing a first digit.
Explain why prefix, suffix and equal block length let a two-element comparison decide a global arrangement, and why each corrective swap removes exactly one inversion.
Produce both obligations without prompting: the adjacent-swap lemma and transitivity of the rule. Being able to say what goes wrong when a pairwise rule is not an ordering is the distinguishing answer here.
Set the bar for pairwise-rule greedies in your codebase: any custom ordering rule ships with an argument that it is a genuine total order, because a subtly non-transitive rule fails intermittently and its bugs are nearly impossible to reproduce.
## The problem shape You hold a set of digit segments — think of version fragments like `9`, `95`, `958` — and you must order them so that the concatenation, read as one number, is as large as possible. The greedy is a sort with an unusual ordering rule: put `a` before `b` exactly when the digit string `a+b` is greater than `b+a`. It is one line of code and it looks like magic. Interviewers ask why it works, and "I compared prefixes and it seemed right" is not an answer. ## Why the naive rules fail Ordering by numeric value, by length, or by leading digit all break. With `9` and `95`: `9` then `95` gives `995`; `95` then `9` gives `959`. Neither value nor length picks the winner. What the pairwise rule does is ask directly which of the two possible local arrangements produces the bigger text, and that turns out to be the only thing that matters. ## The context-independence lemma Fix any ordering and pick two **adjacent** segments `a` and `b`. The two candidate outputs are ``` P + a + b + S and P + b + a + S ``` where `P` is everything before the pair and `S` everything after. Both are the same total length, they share the prefix `P` character for character, and they share the suffix `S`. Therefore the first position where they can possibly differ lies inside the swapped block, and everything after the block is identical. Comparing the two whole results reduces exactly to comparing `a+b` against `b+a`. One more detail makes that comparison safe: `a+b` and `b+a` have the same length, `|a| + |b|`. For equal-length digit strings, lexicographic comparison and numeric comparison agree, so there is no leading-zero or magnitude trap in the comparison itself. This lemma is the whole reason a *pairwise* rule can decide a *global* arrangement: the benefit of ordering two neighbours one way rather than the other does not depend on what surrounds them. ## The adjacent-swap induction Now argue by exchange. Take any ordering `O` that is not sorted by the rule. Then `O` contains at least one adjacent pair in the wrong order — this is the standard fact behind bubble-style sorting: if no adjacent pair is inverted under a transitive rule, the whole sequence is sorted. Swap that pair. By the lemma the result does not decrease. The number of inverted pairs drops by exactly one, since an adjacent swap changes the relative order of that pair and of no other. Inversions are a non-negative integer, so after finitely many such swaps you reach the sorted ordering, and no step along the way lost value. Conclusion: the sorted ordering is at least as good as any ordering, so the greedy is optimal. Note the familiar shape — this is an exchange argument with the swap restricted to adjacent positions, and the decreasing measure is the inversion count rather than "position of first disagreement". ## The obligation everyone forgets: transitivity Sorting by a pairwise rule presupposes that the rule *is* an ordering. Concretely, if `a` beats `b` and `b` beats `c`, then `a` must beat `c`. If that fails, three unfortunate things happen at once: the notion of "sorted" is no longer well defined, different sorting procedures legitimately produce different outputs on the same input, and the "no adjacent inversion implies sorted" step of the argument is simply false — you can have a cyclically-inverted arrangement with no adjacent pair to fix. For this rule transitivity does hold and is provable, which is what licenses the sort. The reusable lesson is that *every* greedy of the form "sort by a pairwise rule and take them in order" carries two proof obligations, not one: the adjacent-swap lemma, and that the rule is a genuine total order. Candidates almost always produce the first and almost never mention the second, and it is the second that separates a memorised solution from an understood one. ## Ties and edge cases When `a+b` equals `b+a`, the two orders give literally identical results, so the swap is neutral. "No worse" is all the exchange needs, and the inversion measure still terminates. Separately, an all-zero input concatenates to a string of zeros; that is a formatting decision about the output, not a flaw in the ordering argument. ## Saying it in an interview Three beats, in order: the context cancels because prefix, suffix and total length are shared; therefore any adjacent inversion can be swapped away without loss; therefore the sorted order is maximal — provided the rule is transitive, which must be checked before you are allowed to sort by it at all.
- Why does the surrounding text not affect which of the two adjacent orders is better?Both candidates share the prefix before the pair and the suffix after it, and the swapped block occupies the same span because `a+b` and `b+a` have equal length. The first differing character therefore lies inside the block, and comparing the two whole results reduces to comparing `a+b` with `b+a`. Equal length also means lexicographic comparison of those two blocks agrees with numeric comparison.
- What breaks if the pairwise rule is not transitive?Sorted order stops being well defined: different procedures produce different outputs on the same input, and the step 'no adjacent inversion implies globally sorted' becomes false, since a cycle can leave every adjacent pair locally fine. You must prove transitivity, or derive the rule from a numeric key, before you are entitled to sort by it.
- Does the argument still work when two segments tie under the rule?Yes. When `a+b` equals `b+a` the two arrangements produce identical results, so the swap is neutral and the exchange's 'no worse' obligation is met. The inversion count still decreases on each corrective swap, so the induction terminates exactly as before.
- Why is the swap restricted to adjacent segments rather than any two?Because adjacency is what makes the context cancel: only neighbours can be exchanged while leaving the rest of the arrangement character-for-character identical. A non-adjacent swap moves everything between them, so the comparison no longer reduces to two blocks, and the inversion count can change by more than one.
saying these in an interview costs you the question
- Says the rule works because bigger leading digits come first
- Compares segments by numeric value or by length
- Never checks that the pairwise rule is transitive
- Swaps non-adjacent segments and claims context still cancels
- Argues from a handful of examples rather than the swap lemma
- Claims the swapped result must be strictly larger