Largest Number Arrangement
Problem
Given non-negative whole numbers, glue them together in some order so the resulting number is as large as possible, and return it as text. Each number is used exactly once and its own digits are never rearranged. A result made only of zeros must read as a single zero.
Examples
Input: nums = [3, 30, 34, 5, 9]
Output: "9534330"
Why: 34 must come before 3, which must come before 30Input: nums = [10, 2]
Output: "210"
Why: the larger number is not the one that belongs firstInput: nums = [0, 0]
Output: "0"
Why: edge case, gluing zeros must not produce a padded resultHints
0 / 3
Ordering by size fails, and so does ordering by first digit alone. The right question is always about a pair: which of two numbers should be glued in front of the other.
For a pair, there are only two possible results, so compare those two glued texts directly and prefer whichever is larger.
Turn every number into text and sort with that pairwise rule as the comparison, which places every number correctly because the rule is consistent across the whole list. Glue the sorted texts together, then collapse a result of nothing but zeros into a single zero.
Solution
Ordering by value is wrong, but the pairwise question has an exact answer: a should precede b when a glued in front of b reads larger than the other way round. That rule is a valid ordering, so handing it to the sort places every number correctly in one go. The only wrinkle is an input of all zeros, where gluing produces a run of zeros that must collapse to a single one. Time is O(n log n) comparisons on short texts, and space is O(n).
from functools import cmp_to_key
def largest_arrangement(nums):
words = [str(x) for x in nums]
# a comes first when gluing it in front produces the larger text
def order(a, b):
return (b + a > a + b) - (b + a < a + b)
words.sort(key=cmp_to_key(order))
glued = "".join(words)
return glued.lstrip("0") or "0" # all zeros must not collapse to nothing
print(largest_arrangement([3, 30, 34, 5, 9])) # -> 9534330
print(largest_arrangement([10, 2])) # -> 210
print(largest_arrangement([0, 0])) # -> 0Stuck on the idea rather than the code? Which Sort When? covers it.