Largest Concatenation — Solution & Editorial

Back to the Problem

Sort with the comparator: x before y iff the string x+y > y+x. This order is total and transitive, and any out-of-order adjacent pair could be swapped to improve — the exchange argument.

Complexity: O(N log N · |digits|)

Watch out: Comparing numerically (9 < 10) is wrong: 9 must come before 10 because 910 > 109. Also collapse the all-zero case to a single 0.