MediumArraysSortingGreedyStrings

Largest Number

1 approach, code in every language

Given a collection of non-negative integers, arrange them so that gluing their decimal representations together produces the largest possible number. Return the result as a string, because it can be far too long to fit in a normal integer.

Watch out for the all-zero case: if every value is zero the answer should be a single "0" rather than a run of zeros.

Example 1

Input: nums = [3,30,34,5,9]

Output: "9534330"

Ordering the pieces as 9, 5, 34, 3, 30 yields the biggest concatenation.

Example 2

Input: nums = [10,2]

Output: "210"

Constraints

1 ≤ nums.length ≤ 100
0 ≤ nums[i] ≤ 10^9

Custom Comparator Sort

Sort the numbers as strings using the rule that a comes before b whenever a+b reads larger than b+a.

Loading animation…

Intuition

The tricky part is deciding the order between values like 3 and 30. Comparing their lengths or numeric values does not directly reveal which arrangement is bigger, but comparing the two possible concatenations does: place a before b exactly when the string a+b is greater than b+a. This pairwise rule is consistent enough to sort the entire list, and once sorted in descending order, joining the pieces gives the maximum number. A final guard covers the case where the biggest piece is "0", meaning every value was zero.

Algorithm walkthrough

1Convert every integer to its string form.
2Sort the strings with a comparator that puts a ahead of b when a+b compares greater than b+a.
3Concatenate the sorted strings in order.
4If the first character is '0', the whole result is zeros, so return the single string "0".
5Otherwise return the concatenation as the answer.

Implementation

from functools import cmp_to_key

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        strs = list(map(str, nums))

        def compare(a, b):
            if a + b > b + a:
                return -1
            if a + b < b + a:
                return 1
            return 0

        strs.sort(key=cmp_to_key(compare))
        result = "".join(strs)
        return "0" if result[0] == "0" else result

Time

O(n log n * k)

Space

O(n * k)

k is the average digit length; each comparison concatenates two strings.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Arrays

After the pattern

Now solve one you haven't seen.

Greatest Shipment Tag is our own problem on the technique behind Largest Number: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free