The whole problem is one idea: the numbers cannot be ordered by their own value. Try comparing 3 and 30. As integers you would say 30 is bigger, so 30 should come first — but 30, 3 concatenates to 303 while 3, 30 gives 330, and 330 is the larger number. The moment you stack two of them back to back you see why: the digits leak into each other, so the length of one number changes how much the other is worth.
That is exactly what the custom comparator checks. For any two strings a and b, decide who leads by comparing the two concatenations a + b and b + a — the one whose concatenation is bigger goes first. Order the whole list so every adjacent pair agrees on that rule, concatenate left to right, and you get the largest number. Two subtleties make the trap: the comparator is not actually transitive (which means you must sort the whole list, not just eyeball neighbors), and if the winner of the sort starts with 0, every number is 0 and you must return "0", not a string of zeros.
Brute Force: Try Every Ordering
Time O(n!)Space O(n)There are only two things a pair can contribute to the rule: one order or the other. A naive solver enumerates every permutation of the numbers, concatenates each one, and keeps the largest string it sees. It is a correct proof by exhaustion — the optimal ordering must be one of the n! arrangements — but it scales catastrophically.
from itertools import permutations
def largest_number(nums): best = "" for p in permutations(nums): s = "".join(map(str, p)) best = max(best, s) # every permutation has the same length return best.lstrip("0") or "0" # all-zeros edge -> "0"Why it is factorial: there are n! permutations and each concatenation costs O(total digits), giving O(n! · M) time where M is the total number of digits — useless for n up to 100. The .lstrip("0") guards the all-zeros case, but the work itself is the lesson here: you never need to look at whole orderings, only at pairwise relationships.
Custom Comparator Sort
OptimalTime O(n log n)Space O(n)Sort the numbers, but tell the sort how to compare: define that a should come before b whenever a + b beats b + a as strings. Then a standard sort produces the unique order where concatenating left to right is the largest number.
from functools import cmp_to_key
def cmp(a, b): if a + b > b + a: # a leads -> a sorts before b return -1 if a + b < b + a: # b leads return 1 return 0 # tied concatenations: either order is fine
def largest_number(nums): strs = list(map(str, nums)) strs.sort(key=cmp_to_key(cmp)) return "0" if strs[0] == "0" else "".join(strs)Watch the two-chip case first — it pins down what the comparator even means — then the full example, where the same rule is applied pair by pair to reach the answer:
settled prefix builds left to right — every adjacent pair agrees on the comparator
Two numbers, one order question: which way round makes the bigger concatenation? 10 then 2 gives 102, but 2 then 10 gives 210 — a factor of two even though both use the same digits. The whole problem is choosing an order over the whole list.
The full example [3,30,34,5,9], sorted one comparison at a time. Notice the moment 5 slides past 30 even though 30 is the bigger integer — the comparator is judging concatenations, not values:
settled prefix builds left to right — every adjacent pair agrees on the comparator
Build the largest concatenation from 3, 30, 34, 5, 9. The trap: a plain sort would compare 30 against 5 and 3 by string value — where 30 is bigger than 5 — and get the answer wrong. Every pair must be judged by its concatenations instead.
Why it is O(n log n): converting to strings is O(M) (M = total digits). The comparator itself is O(1) amortized in string length for any two strings (just two concatenations), and the sort does O(n log n) of those comparisons, giving O(n log n · L) where L is the average digit count. The .join walks the sorted result for another O(M) time; total space is O(M) for the string array and the result. The single guard line if strs[0] == "0" collapses the degenerate all-zeros case — if the leading element is 0, every element is 0, so the largest number is just "0".