172. Largest Number
You are given a list of non-negative integers nums. Line them up in some order and read their digits left to right as one long decimal number — your job is to pick the ordering that makes that number as large as possible, and return it as a string (it can easily overflow every built-in integer type).
One wrinkle: if every entry is 0, the concatenation would look like "000…0". In that case return exactly "0".
Ordinary numeric sorting will betray you here — 9 must beat 30 for the front spot even though 9 < 30. Finding the comparison that actually works is the whole problem.
Example 1:
Input: nums = [10, 2]
Output: "210"
Explanation: The two candidate orders read as 210 and 102; putting 2 first wins.
Example 2:
Input: nums = [3, 30, 34, 5, 9]
Output: "9534330"
Explanation: The winning order is 9, 5, 34, 3, 30. Note that 3 goes before 30, because 330 beats 303.
Example 3:
Input: nums = [0, 0]
Output: "0"
Explanation: Both orders read "00"; the all-zero case collapses to "0".
Constraints:
- 1 ≤ nums.length ≤ 100
- 0 ≤ nums[i] ≤ 10⁹
Hints:
Sorting by numeric value fails (9 belongs before 30), and sorting plain strings lexicographically fails too (is "3" before or after "30"? It depends on what follows). What question actually decides which of two numbers should stand first?
For two numbers as strings a and b, only two arrangements of the pair exist: a+b and b+a. Put a first exactly when the string a+b is greater than b+a. This comparison is a valid total order (it is transitive), so any sort can use it.
After sorting and joining, one edge remains: [0, 0, …] would produce "00…0". If the result starts with '0', return "0".
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [10, 2]
Expected output: "210"