179. Largest Number
Problem Description
The problem presents us with a list of non-negative integers called nums
. We're tasked with rearranging these integers to create the largest possible number when they're concatenated together. It's important to realize that simply sorting the integers in descending order won't work because when concatenating numbers, the order in which we join them affects the final result. For example, '9' and '34' form a larger number when concatenated as '934' rather than '349'. As a final result can be extremely large, we must return it as a string instead of an integer.
Intuition
To find the correct order to concatenate the numbers to form the largest number, we need to determine a sorting strategy that compares combinations of two numbers. This strategy should allow us to understand which two numbers will produce a larger number when placed one after the other.
The intuition here is to design a custom sorting function that compares two strings—representations of the numbers—and decides which combination (either a + b
or b + a
) creates a larger number. For instance, when comparing 9
and 34
, we check if 934
is larger than 349
, so we can position 9
before 34
in the final arrangement.
We apply this custom sorting method to all pairs of numbers in nums
to sort the entire list in such a way that concatenating the sorted elements yields the largest number.
The last caveat to address is when the list of numbers begins with one or multiple '0's due to the sorting, which would lead to a result starting with '0' (like '00' or '000'). The correct output should just be '0'. To solve this, we check the first element of the sorted array—if it's '0', we return '0' as the result, otherwise, we join all numbers into a string and return it.
Solution Approach
The solution implements a sorting strategy that targets the specific needs of the problem. Since we need to arrange the numbers to form the largest number possible when concatenated, we convert the integers to strings to allow for comparison concatenation.
Here's the step by step approach:
- Convert each integer in
nums
to a string. This allows for easy concatenation and comparison. - Sort the string numbers using a custom comparator. This comparator is implemented with a lambda function that takes two string numbers
a
andb
and usescmp_to_key
to convert the comparator result into a key for the sort function. - The lambda function defined for comparison returns
1
ifa + b < b + a
, meaningb
should come beforea
, and-1
ifa + b >= b + a
. Thecmp_to_key
method transforms this comparator to a function that can be used with the list's sort method. - If the first number is '0', it implies that all numbers are zero due to the sorting property, so we return '0'. Otherwise, we concatenate all numbers in a single string. This step ensures we don't end up with leading zeroes in the result.
- Finally, join all string representations of the numbers to form the largest number and return it.
The key to this solution is the custom sort comparator, which isn't straightforward because we're comparing combinations of the numbers. The cmp_to_key
from Python's functools
module is used to convert the lambda function into a key function suitable for the sort method.
Overall, the algorithm's efficiency comes from the sorting, which operates in O(n log n)
time complexity, where n
is the number of elements in nums
. The conversion to strings and the final concatenation of the sorted list have a lower time complexity and therefore don't dominate the time complexity of the whole algorithm.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a simple example using the list nums = [3, 30, 34, 5, 9]
.
-
We begin by converting each integer in
nums
to a string so we'll end up with["3", "30", "34", "5", "9"]
. -
Next, we sort these strings using our custom comparator. This is how the comparisons would look:
- Compare
3
vs30
: Since330
>303
,3
should come before30
. - Compare
3
vs34
: Since334
>343
,3
should come before34
. - Compare
3
vs5
: Since35
<53
,5
should come before3
. - Compare
3
vs9
: Since39
<93
,9
should come before3
.
Continuing with the rest of the list in a similar fashion, our custom comparator will end up ordering our list as
["9", "5", "34", "3", "30"]
. Notice how9
is placed before5
, even though9
is smaller than5
, because95
is larger than59
. - Compare
-
We check if the first element is '0'. If so, the entire list would be zeros, and we would return '0'. In this case, it's not, so we proceed to the next step.
-
Finally, we concatenate all numbers in our sorted array to form the largest number, which is
"9534330"
.
By using this method, we ensure that we consider the best placement of each number to achieve the highest numerical value when the elements are concatenated. The resulting string, "9534330"
, is the largest number that can be formed from the array.
Solution Implementation
1from functools import cmp_to_key
2
3class Solution:
4 def largest_number(self, nums: List[int]) -> str:
5 # Convert all integers to strings for easy concatenation
6 nums_as_str = [str(num) for num in nums]
7
8 # Sort the list of strings, defining a custom comparator
9 # that compares concatenated string combinations
10 nums_as_str.sort(key=cmp_to_key(self._compare_numbers))
11
12 # Special case: if the highest number is "0", the result is "0"
13 # (happens when all numbers are zeros)
14 if nums_as_str[0] == "0":
15 return "0"
16
17 # Join the numbers to form the largest number
18 return "".join(nums_as_str)
19
20 def _compare_numbers(self, a: str, b: str) -> int:
21 # Custom comparator for sorting:
22 # If the concatenation of a before b is less than b before a,
23 # then we say a is "greater than" b in terms of the custom sorting.
24 # That is, return -1 to indicate a should come before b.
25 if a + b < b + a:
26 return 1
27 else:
28 return -1
29
1class Solution {
2 public String largestNumber(int[] nums) {
3 // Create a list of strings to store the numbers as strings
4 List<String> stringNumbers = new ArrayList<>();
5
6 // Convert each integer in the array to a string and add it to the list
7 for (int num : nums) {
8 stringNumbers.add(String.valueOf(num));
9 }
10
11 // Sort the list using a custom comparator
12 // The custom comparator defines the order based on the concatenation result
13 // This ensures that the largest number is formed after sorting
14 stringNumbers.sort((str1, str2) -> (str2 + str1).compareTo(str1 + str2));
15
16 // After sorting, if the largest number is "0", it means all numbers were zeros
17 // In that case, return "0"
18 if ("0".equals(stringNumbers.get(0))) {
19 return "0";
20 }
21
22 // Join all the strings in the list to get the final largest number representation
23 return String.join("", stringNumbers);
24 }
25}
26
1#include <vector>
2#include <string>
3#include <algorithm>
4
5class Solution {
6public:
7 // Takes a vector of integers and returns the largest number possible
8 // by concatenating their string representations
9 string largestNumber(vector<int>& nums) {
10 // Convert integers to strings
11 vector<string> stringNums;
12 for (int num : nums) {
13 stringNums.push_back(to_string(num));
14 }
15
16 // Sort the strings based on a custom comparison function
17 sort(stringNums.begin(), stringNums.end(),
18 [](const string& a, const string& b) {
19 // The 'larger' number is the one that leads to a bigger
20 // concatenated string
21 return a + b > b + a;
22 });
23
24 // If after sorting the biggest number is "0",
25 // the result is "0" (because all numbers are zeros)
26 if (stringNums[0] == "0") {
27 return "0";
28 }
29
30 // Build the largest number by concatenating sorted strings
31 string result;
32 for (const string& numStr : stringNums) {
33 result += numStr;
34 }
35
36 return result;
37 }
38};
39
1function largestNumber(nums: number[]): string {
2 // Convert integers to strings
3 const stringNums: string[] = nums.map(num => num.toString());
4
5 // Custom comparison function for sorting
6 const compare = (a: string, b: string): number => {
7 const concat1 = a + b;
8 const concat2 = b + a;
9 // If concat1 is 'greater' than concat2 in terms of
10 // lexicographic order, it should come first
11 return concat1 > concat2 ? -1 : (concat1 === concat2 ? 0 : 1);
12 };
13
14 // Sort the strings based on the custom comparison function
15 stringNums.sort(compare);
16
17 // Check if the largest element is "0", the result must be "0"
18 // since all numbers would be zeros
19 if (stringNums[0] === "0") {
20 return "0";
21 }
22
23 // Build the largest number by concatenating sorted strings
24 const result = stringNums.join('');
25
26 return result;
27}
28
Time and Space Complexity
Time Complexity
The time complexity mainly depends on the sorting function. In the above code, the sorting function uses a custom comparator which is used to decide the order based on the concatenation of two numbers as strings.
- Converting all integers in the list to strings takes
O(N)
time, whereN
is the number of elements innums
. - Sorting in Python usually has a time complexity of
O(N log N)
. However, the comparator itself is a lambda function that concatenates strings, which takesO(k)
time, wherek
is the average length of the strings (or the average number of digits in the numbers). Therefore, the sorting step takesO(N log N * k)
. - The join operation on the sorted strings takes
O(N * k)
time.
Hence, the overall time complexity is O(N log N * k)
, where N
is the number of elements in nums
, and k
is the average number of digits in those elements.
Space Complexity
The space complexity of the code also has several components:
- Creating a new list of strings requires
O(N * k)
space. - The sort operation might use additional space for its internal operations. In the worst case, the sorting algorithm might take
O(N * k)
space. - The output string takes
O(N * k)
space.
Thus, the overall space complexity would be O(N * k)
, taking into consideration the space used by the list of strings and the potential internal space used by the sorting algorithm.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of these properties could exist for a graph but not a tree?
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.