Largest Number
Medium · Arrays & Hashing · Array · String · Greedy · Sorting
Problem
You are given a list of non-negative integers nums. Arrange them so that, written one after another, they form the largest possible number, and return that number as a string. The result can be far too big for any integer type.
The answer must not have leading zeros: if every number is 0, return "0".
Examples
Input: nums = [5,56,9] Output: "9565"
9 leads, and 56 goes before 5 because "565" > "556".
Input: nums = [12,121] Output: "12121"
"12121" beats "12112", so 12 goes first.
Input: nums = [0,0,0] Output: "0"
Leading zeros collapse to a single "0".
Constraints
- 1 <= len(nums) <= 100
- 0 <= nums[i] <= 10^9
Approaches
- Baseline: pick the best leading piece, one at a time — time O(n² · L), space O(n · L)
Follow-up
Why is the comparison "a + b > b + a" transitive? Write each piece as a number and show that the rule is the same as comparing a / (10^len(a) - 1) with b / (10^len(b) - 1), an ordinary order on real numbers.
Related problems
Start free on Cariara · Coding problems · System design studio
