Coding questions · LinkedIn
Arrange Nonnegative Integers to Form the Largest Number
Arrange nonnegative integers so their decimal strings form the largest possible concatenation. The prompt requires every value exactly once, returns a string for unbounded result length, defines the all-zero case, and includes order-sensitive examples.
Given a list of nonnegative integers, arrange all of them so that their decimal representations concatenate into the numerically largest possible value.
Implement:
largestConcatenatedNumber(nums) -> string
Return a string because the result may exceed integer limits. If every input value is zero, return exactly "0". Every input element must be used once.
Constraints
1 <= nums.length <= 100,0000 <= nums[i] <= 10^9
Examples
Example 1
nums = [10, 2]
output = "210"
Example 2
nums = [3, 30, 34, 5, 9]
output = "9534330"
Arrange Nonnegative Integers to Form the Largest Number
Hints
- For two decimal strings a and b, compare a+b with b+a.
- Handle the all-zero input with the required canonical output.
Approach
Convert each value to its decimal string. For any two strings a and b, place a before b exactly when a+b is larger than b+a. Sorting by this comparison gives a globally maximal concatenation: if adjacent strings violate the comparison, swapping them makes the whole result larger, so no maximal order can contain such an inversion. Join the sorted strings. If the first string is 0, every value was zero, so return the single canonical string "0".
- Time complexity: O(n log n * d), where d is at most the combined digit length compared for a pair.
- Space complexity: O(n * d) for the decimal strings and sorting storage.