Largest Number

Question Description

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.

Solution

Just add an additional comparator to compare the numbers in string format. Do it in greedy way by comparing the a + b and b + a.

Important Note for corner cases: Be careful when strip the extra '0's in result string and we should return '0' even when the array is empty.

class Solution(object):
    def largestNumber(self, nums):
        def comparator(num1, num2):
            if num2 + num1 > num1 + num2:
                return 1
            elif num2 + num1 < num1 + num2:
                return -1
            else:
                return 0
        """
        :type nums: List[int]
        :rtype: str
        """
        for i in range(len(nums)):
            nums[i] = str(nums[i])
        nums.sort(comparator)
        return ''.join(nums).lstrip('0') or '0'