Largest Number

Question

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"

Solution

Intuition

Basically for this question we want to sort.

For example if we have

3 20 4 5
_ _ _ _ _

We basically want to see which number can go first so that it makes the combination greatest

Say we pick any 2 numbers, such as 4 vs 20

We want to see if we should put it 420 or 204. Of course, 420 would be better. Hence the sorting strategy.

Implementation

from functools import cmp_to_key

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

        for i in range(len(nums)):
            numStr.append(str(nums[i]))
        
        numStr.sort(key=cmp_to_key(self.compare))

        return str(int("".join(numStr)))

    def compare(self, a, b):
        if int(a + b) > int(b + a):
            return -1
        return 1

[!note]
In the compare function, if you want a to go first then you return -1 if you want a to go second then you return 1

Since a goes first indicates that a is smaller, we want to return -1