Largest Number

2 min read
Array
Greedy
LC-Medium

Oct 21, 2022

3 years ago

LeetCode

Solution

I tried getting the frequency of each digit and then creating the string by iterating from 9 to 1, but this doesn't work for double digits and above, since "30" would convert to one instance of 3 and one instance of 0. If there's a 1 and 2, they would come in between the 3 and the 0, which should not happen, we need to maintain the "integrity" of the number, so to speak.
I also tried lexicographically sorting the numbers array using nums.sort(key=str), and then creating the string by iterating from the back, but this also doesn't work because in lexicographical order, 30 is bigger than 3, so we'd have "303" but putting the 3 first would create a bigger number "330"
Solution is to just use a custom sort function where given two numbers a and b, you create integers from the strings and check which one is bigger between int(f'{a}{b}') and int(f'{b}{a}')

Time	Space	Explanation
`O(n log n)`	`O(n)`	Extra space is for sorting nums

def largestNumber(self, nums: List[int]) -> str: def compare(a, b): num1, num2 = int(f'{a}{b}'), int(f'{b}{a}') if num1 < num2: return -1 elif num1 > num2: return 1 return 0 nums = sorted(nums, key=cmp_to_key(compare), reverse=True) if nums[0] == 0: # Edge case where first number is 0, return '0' return ''.join(list(map(lambda x: str(x), nums)))