Given a list of non negative integers, arrange them such that they form the largest number.
For example, given
[3, 30, 34, 5, 9], the largest formed number is
Note: The result may be very large, so you need to return a string instead of an integer.
Special thanks to @ts for adding this problem and creating all test cases.
To construct the largest number, we want to ensure that the most significant\ndigits are occupied by the largest digits.\n
First, we convert each integer to a string. Then, we sort the array of strings.\n
While it might be tempting to simply sort the numbers in descending order,\nthis causes problems for sets of numbers with the same leading digit. For\nexample, sorting the problem example in descending order would produce the\nnumber , while the correct answer can be achieved by transposing\nthe and the . Therefore, for each pairwise comparison during the\nsort, we compare the numbers achieved by concatenating the pair in both\norders. We can prove that this sorts into the proper order as follows:\n
Assume that (without loss of generality), for some pair of integers and\n, our comparator dictates that should precede in sorted\norder. This means that (where represents\nconcatenation). For the sort to produce an incorrect ordering, there must be\nsome for which precedes and precedes . This is a\ncontradiction because and \nimplies . In other words, our custom comparator\npreserves transitivity, so the sort is correct.\n
Once the array is sorted, the most "signficant" number will be at the front.\nThere is a minor edge case that comes up when the array consists of only\nzeroes, so if the most significant number is , we can simply return\n. Otherwise, we build a string out of the sorted array and return it.\n\n
Time complexity : \n\n
Although we are doing extra work in our comparator, it is only by a\nconstant factor. Therefore, the overall runtime is dominated by the\ncomplexity of
sort, which is in Python and Java.
Space complexity : \n\n
Here, we allocate additional space to store the copy of
nums.\nAlthough we could do that work in place (if we decide that it is okay to\nmodify
nums), we must allocate space for the final return\nstring. Therefore, the overall memory footprint is linear in the length\nof
Analysis and solutions written by: @emptyset\n