Given a list of non-negative integers nums, arrange them such that they form the largest number and return it.
Since the result may be very large, so you need to return a string instead of an integer.
Example 1:
Input: nums = [10,2] Output: "210"
Example 2:
Input: nums = [3,30,34,5,9] Output: "9534330"
Constraints:
1 <= nums.length <= 1000 <= nums[i] <= 109In #179 Largest Number, the challenge is to arrange a list of non‑negative integers so they form the largest possible number when concatenated. A simple numerical sort does not work because the order between two numbers depends on their combined string result. For example, deciding between 3 and 30 requires comparing "330" and "303".
The key idea is to convert numbers to strings and sort them using a custom comparator. For any two numbers a and b, compare a + b with b + a. If a + b is larger, a should come before b. This greedy ordering ensures that each local choice contributes to the globally largest concatenated number.
After sorting, concatenate all strings to build the final result. A special edge case occurs when the largest element is "0", meaning the entire number should simply be "0". The dominant cost comes from sorting with the custom comparison.
Time Complexity: O(n log n * k), where k is the average string length. Space Complexity: O(n) for storing string representations.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Custom Sorting with Concatenation Comparison | O(n log n * k) | O(n) |
Sahil & Sarra
This approach involves converting each number to a string and sorting them based on a custom comparator. The key idea is to determine the order of two numbers a and b by comparing the concatenated results a+b and b+a as strings. Sorting the numbers in such a manner ensures that the concatenated string is the largest possible.
Time Complexity: O(n log n), where n is the number of elements, due to sorting. Comparison operation within the sort is O(1) as it's based on string concatenation and comparison.
Space Complexity: O(n), where n is the number of integers, due to the storage of string representations of integers.
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5
6using namespace std;
7
8string largestNumber(vector<int>& nums) {
9 vector<string> numStrs;
10 for (int num : nums) {
11 numStrs.push_back(to_string(num));
12 }
13 sort(numStrs.begin(), numStrs.end(), [](const string& a, const string& b) {
14 return a + b > b + a;
});
if (numStrs[0] == "0") {
return "0";
}
string result;
for (const string& numStr : numStrs) {
result += numStr;
}
return result;
}
int main() {
vector<int> nums = {3, 30, 34, 5, 9};
cout << largestNumber(nums) << endl;
return 0;
}The solution involves converting integers to strings, and then sorting the strings with a custom comparator to ensure the largest concatenated order. The comparator checks which of the two possible concatenated results is larger and arranges based on that. Finally, it concatenates the sorted array to get the result.
This approach involves using a custom comparator with a min-heap to continuously extract the largest possible number combination. This can be more efficient in some cases where we require efficient access to the largest current element for concatenation.
Time Complexity: O(n log n), dominated by the heap operations.
Space Complexity: O(n) due to the heap storage.
1import heapq
2
3def largestNumber(nums):
4 if
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of the Largest Number problem are commonly asked in coding interviews at companies like Amazon, Google, and Meta. It tests understanding of custom sorting, greedy reasoning, and handling edge cases with strings.
The optimal approach converts all integers to strings and sorts them using a custom comparator. For two numbers a and b, compare the concatenations "a+b" and "b+a" to decide the order. This ensures the final concatenated result forms the largest possible number.
Normal numerical sorting does not account for how numbers interact when concatenated. For example, 9 should come before 34 because "934" is larger than "349". A custom string comparison is required to capture this behavior.
The solution typically uses an array or list of strings after converting the integers. Sorting with a custom comparator is the main operation, and the final answer is built by joining the sorted strings together.
The solution uses a max-heap implemented with negative values in Python’s built-in heapq, to facilitate priority retrieval of the ‘largest’ lexical integer string. The heap ensures the largest value is popped and concatenated first.