Largest Number

Problem

A financial reporting tool needs to display account balances as the largest possible combined value by reordering the figures. Given a list of non-negative integers, arrange them to form the largest possible number and return it as a string.

Example 1:

Input: [12, 3]
Output: "312"

Example 2:

Input: [4, 40, 45, 7, 8]
Output: "8745440"

Example 3:

Input: [0, 0]
Output: "0"
Explanation: All zeros collapse to a single "0" instead of "00".

Constraints:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 10^9

Solution Breakdown

Approach: Custom comparator sort via functools.cmp_to_key.

The largest concatenation is built by sorting the numbers under a pairwise rule rather than by their numeric value. For any two numbers a and b, a should come before b exactly when the string str(a) + str(b) is lexicographically larger than str(b) + str(a) - that is, when putting a first yields the bigger combined number. The compare(a, b) function returns -1 in that case (a precedes b) and 1 otherwise, and cmp_to_key wraps it so sorted can apply it. Once every adjacent pair satisfies this relation, joining the numbers left to right produces the maximum possible number. Trace [4, 40, 45, 7, 8]: comparing 4 and 40 gives "440" > "404", so 4 precedes 40; comparing 8 against everything wins, so 8 leads. The sort settles to [8, 7, 45, 4, 40], which joins to "8745440".

Why a comparator and not a key= function: the decision depends on both elements at once (a+b vs b+a), a relation no per-element key can capture. The comparator is transitive, so the global sort is well defined. String comparison naturally handles different lengths - "9" > "30" because '9' > '3' at position 0 - which is exactly the ordering this problem needs.

Edge cases: All zeros - [0, 0] joins to "00", so the leading-zero check "0" if result[0] == "0" else result collapses it to "0". A single element returns its own digits.

Complexity: O(nk log n) time, O(n) space - n log n comparisons, each comparing two k-digit strings; the output and decorated list are O(n).