179. Largest Number


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 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.


Approach #1 Sorting via Custom Comparator [Accepted]

Intuition

To construct the largest number, we want to ensure that the most significant digits are occupied by the largest digits.

Algorithm

First, we convert each integer to a string. Then, we sort the array of strings.

While it might be tempting to simply sort the numbers in descending order, this causes problems for sets of numbers with the same leading digit. For example, sorting the problem example in descending order would produce the number , while the correct answer can be achieved by transposing the and the . Therefore, for each pairwise comparison during the sort, we compare the numbers achieved by concatenating the pair in both orders. We can prove that this sorts into the proper order as follows:

Assume that (without loss of generality), for some pair of integers and , our comparator dictates that should precede in sorted order. This means that (where represents concatenation). For the sort to produce an incorrect ordering, there must be some for which precedes and precedes . This is a contradiction because and implies . In other words, our custom comparator preserves transitivity, so the sort is correct.

Once the array is sorted, the most "signficant" number will be at the front. There is a minor edge case that comes up when the array consists of only zeroes, so if the most significant number is , we can simply return . Otherwise, we build a string out of the sorted array and return it.

Complexity Analysis

  • Time complexity :

    Although we are doing extra work in our comparator, it is only by a constant factor. Therefore, the overall runtime is dominated by the complexity of sort, which is in Python and Java.

  • Space complexity :

    Here, we allocate additional space to store the copy of nums. Although we could do that work in place (if we decide that it is okay to modify nums), we must allocate space for the final return string. Therefore, the overall memory footprint is linear in the length of nums.

Analysis and solutions written by: @emptyset

Submit Solution