Given a list of non negative integers, arrange them such that they form the largest number.

Example 1:


Input: [10,2]
Output: "210"

Example 2:


Input: [3,30,34,5,9]
Output: "9534330"


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

Difficulty: interview

Starter code:

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

Solutions:
class Solution:
     def largestNumber(self, nums):
         """
         :type nums: List[int]
         :rtype: str
         """
         nums = [str(n) for n in nums]
         
         nums.sort(reverse=True)
         
         for i in range(1, len(nums)):
             if len(nums[i-1]) > len(nums[i]):
                 ran = len(nums[i])
                 j = i
                 while j-1 >= 0 and nums[j-1][:ran] == nums[j] and nums[j-1]+nums[j]<=nums[j]+nums[j-1]:
                     nums[j-1], nums[j] = nums[j], nums[j-1]
                     j -= 1
                     
         return str(int(''.join(nums)))

class Solution:
     class MyNumber:
         def __init__(self, v):
             self.str_val = str(v)
             self.val = [int(x) for x in self.str_val]
             self.n = len(self.val)
         def __cmp__(self, other):
             n1 = self.str_val + other.str_val
             n2 = other.str_val + self.str_val            
             return 0 if n1 == n2 else 1 if n1 > n2 else -1
         
 
     def largestNumber(self, nums):
         """
         :type nums: List[int]
         :rtype: str
         """
         if all(x == 0 for x in nums):
             return '0'
         myns = [self.MyNumber(x) for x in nums]
         
         for i in range(len(nums)):
             for j in range(i + 1, len(nums)):
                 if myns[j].__cmp__(myns[i]) > 0:
                     t = myns[i]
                     myns[i] = myns[j]
                     myns[j] = t
 
         return "".join([x.str_val for x in myns])
     


class Solution:
     def largestNumber(self, nums):
         """
         :type nums: List[int]
         :rtype: str
         """
         # maxPos = 0
         # maxNum = ''
         # maxLen = 0
         # maxCut = ''
         # res = ''
         # while nums:
         #     for i in range(len(nums)):
         #         cur = nums[i]
         #         ori = cur
         #         while cur % 10 == 0:
         #             cur = cur // 10
         #         if str(cur) > maxCut or (str(cur) == maxCut and len(str(ori)) < maxLen):
         #             maxCut = str(cur)
         #             maxNum = str(ori)
         #             maxPos = i
         #             maxLen = len(maxNum)
         #     nums.pop(maxPos)
         #     res += maxNum
         #     maxPos = 0
         #     maxNum = ''
         #     maxLen = 0
         #     maxCut = ''
         # return res
 
         maxPos = 0
         maxNum = ''
         res = ''
         while nums:
             for i in range(len(nums)):
                 cur = nums[i]
                 if str(cur) + maxNum >= maxNum + str(cur):
                     maxNum = str(cur)
                     maxPos = i
             nums.pop(maxPos)
             res += maxNum
             maxPos = 0
             maxNum = ''
         if res[0] == '0':
             return '0'
         return res


class Solution:
     def largestNumber(self, nums):
         """
         :type nums: List[int]
         :rtype: str
         """
         
         ## edge case: 981 3,31 331 313
         
         
         strs = [str(num) for num in nums]
         
         def bigger(str1, str2):
             if int(str1+str2) >= int(str2+str1):
                 return str1
             else:
                 return str2
         
         answer = ""
         current = strs
         while current:
             maximum = current[0]
             for i in range(len(current)):
                 maximum = bigger(maximum, current[i])
                 
             answer += maximum
             current.remove(maximum)
         
         if answer[0] == "0":
             return "0"
         return answer

class Solution:
     def largestNumber(self, nums):
         """
         :type nums: List[int]
         :rtype: str
         """
         # case 1  34 vs 34
         #case2: 3 vs 34  ;    34 vs 3;        30 vs 3;  3 vs 30
 
         # this works:
         # compare the element by ourselves according to the rule of largest number first    
         if nums is None or len(nums) == 0:
             return ''
 
         for i in range(len(nums)-1, -1, -1):
             for j in range(len(nums)-1, len(nums)-i-1, -1):
                 #compare element 1, 2
                 e1 = str(nums[j-1])
                 e2 = str(nums[j])
                 #print ("e1, e2: ", e1, e2, nums)
                 if e1+e2 < e2+e1:
                     #swap 
                     t = nums[j]
                     nums[j] = nums[j-1]
                     nums[j-1] = t
 
         ans = ''
         for n in nums:
             if n == 0 and ans == '':
                 continue
             ans += str(n)
         #print ("nums: ", nums)
         return '0' if len(ans) == 0 else ans 


class Solution:
     
     def largestNumber(self, nums):
         """
         :type nums: List[int]
         :rtype: str
         """
         import functools
 #         s_nums = []
 #         maximum_length = 0
 #         result = ""
 #         dic = {}
 #         for i in range(0, len(nums)):
 #             value = str(num[i])
 #             maximum_length = max(maximum_length, len(value))
 #             s_nums.append(value)
 #             dic[i] = True
             
 #         for i in range(0, maximum_length-1): 
 #             temp_max = ""
 #             temp_max_array = []
 #             for j in range(0, s_nums-1):
 #                 try:
 #                     a = s_nums[j][i]
 #                     try:
 #                         b = s_nums[j][i+1]
 #                     except:
 #                         if dic[j] != False:
 #                             temp_max_array.append(nums[j])
 #                             dic[j] = False
 #                         dic[j] += 1
 #                 except:
 #                     continue
 #             print(temp_max_array)
 #             result += ''.join(sorted(temp_max_array))
             
 #         return result
         nums_str = []
         for each in nums:
             nums_str.append(str(each))
         
         result = ''.join(sorted(nums_str, key = functools.cmp_to_key(self.comparator)))
         
         if int(result) == 0:
             return '0'
         else:
             return result
     
     
 
     def comparator(self, a, b):
         
         num1 = a + b
         num2 = b + a
         
         if num1 > num2:
             return -1
         elif num2 > num1:
             return 1
         else:
             return 0
         


class Solution:
     def sorting(self, numstr):
         newnumstr = []
         #print(numstr)
         for i in range(0, len(numstr)):
             for j in range(1, len(numstr)-i):
                 if numstr[j-1] + numstr[j] < numstr[j] + numstr[j-1]:
                     temp = numstr[j-1]
                     numstr[j-1] = numstr[j]
                     numstr[j] = temp
         #print(numstr)
     def largestNumber(self, nums):
         """
         :type nums: List[int]
         :rtype: str
         """
         matrix = dict()
         for num in nums:
             numstr = str(num)
             if numstr[0] not in matrix:
                 matrix[numstr[0]] = []
             matrix[numstr[0]].append(numstr)
         print(matrix)
         
         ret = ""
         for i in range(9, -1, -1):
             if str(i) in matrix:
                 prenums = matrix[str(i)]
                 self.sorting(prenums)
                 #print(prenums)
                 ret += "".join(prenums)
                 #print(ret)
         return str(int(ret))


class Solution:
     def largestNumber(self, nums):
         """
         :type nums: List[int]
         :rtype: str
         """
         def lexic_comp(a, b):
             ab = str(a) + str(b)
             ba = str(b) + str(a)
             if ab > ba:
                 return -1
             elif ba > ab:
                 return 1
             return 0
         
         import functools
         
         nums.sort(key=functools.cmp_to_key(lexic_comp))
         
         return str(int(''.join(map(str, nums))))


class Solution:
     def largestNumber(self, nums):
         """
         :type nums: List[int]
         :rtype: str
         """
         s=self.sort(nums)
         if s.startswith("0"):
             return "0"
         else:return s
     def sort(self,nums):
         if not nums:return ""
         else:
             pivot=nums[0]
             left=[]
             right=[]
             for i in range(1,len(nums)):
                 if self.compare(nums[i],pivot):
                     left.append(nums[i])
                 else:
                     right.append(nums[i])
             return self.sort(left)+str(pivot)+self.sort(right)
             
     def compare(self,num1,num2):
         num1,num2=str(num1),str(num2)
         return int(num1+num2)>int(num2+num1)

class Solution:
     def largestNumber(self, nums):
         """
         :type nums: List[int]
         :rtype: str
         """
         def cmp_to_key(mycmp):
             'Convert a cmp= function into a key= function'
             class K:
                 def __init__(self, obj, *args):
                     self.obj = obj
                 def __lt__(self, other):
                     return mycmp(self.obj, other.obj) < 0
                 def __gt__(self, other):
                     return mycmp(self.obj, other.obj) > 0
                 def __eq__(self, other):
                     return mycmp(self.obj, other.obj) == 0
                 def __le__(self, other):
                     return mycmp(self.obj, other.obj) <= 0
                 def __ge__(self, other):
                     return mycmp(self.obj, other.obj) >= 0
                 def __ne__(self, other):
                     return mycmp(self.obj, other.obj) != 0
             return K
         
         def compare(n1, n2):
             #print(n1, n2, ":")
             l1 = len(n1)
             l2 = len(n2)
             i = 0
             if l1 != l2:
                 tmp = n1 
                 n1 = n1 + n2
                 n2 = n2 + tmp
                 l1 = l1 + l2
             #print(n1, n2)
             while i < max(l1, l2):
                 #print(i, n1[i], n2[i])
                 if n1[i] < n2[i]:
                     #print(n1, "<", n2)
                     return -1
                 elif n1[i] > n2[i]:
                     #print(n1, ">", n2)
                     return 1
                 i += 1
             #print(n1, "=", n2)
             return 0
             
         
         def convert(num):
             if num == 0:
                 return [0]
             res = []
             while num:
                 res.append(num % 10)
                 num //= 10
             res.reverse()
             return res
         
         nums = list(map(convert, nums))
         nums.sort(key=cmp_to_key(compare), reverse=True)
         print(nums)
         res = [str(c) for num in nums for c in num]
         
         res =  "".join(res).lstrip('0')
         if not res:
             res = '0'
         return res

class Solution:
     def largestNumber(self, nums):
         """
         :type nums: List[int]
         :rtype: str
         """
         s=self.sort(nums)
         if s.startswith("0"):
             return "0"
         else:return s
     def sort(self,nums):
         if not nums:return ""
         else:
             pivot=nums[0]
             left=[]
             right=[]
             for i in range(1,len(nums)):
                 if self.compare(nums[i],pivot):
                     left.append(nums[i])
                 else:
                     right.append(nums[i])
             return self.sort(left)+str(pivot)+self.sort(right)
             
     def compare(self,num1,num2):
         return int(str(num1)+str(num2))>int(str(num2)+str(num1))