Largest Number

Problem

Qn - Largest Number

Approach

My original thought was that I could just convert them to strings and then sort them by lexicographic order and join them back into a string. But realised that there are some edge cases which was not covered. ie like ‘3’ vs ‘30’. Lexicographic order dictates that ‘30’ comes after ‘3’, and since we reverse the order to get the largest first, it ends up that in our order ‘30’ will come first then ‘3’, but that’s not what we want. We want ‘3’ to come first since ‘30’ will set the next digit to ‘0’ which would be smaller than ‘3’.

I decided to make my own comparator to deal with this “special case”, which got messy pretty quickly.

Watched a neetcode video, and damm the solution was pretty easy to understand and easy to code out, and I feel like it is doable to think of it. Instead of trying to find out digit by digit, we can just solve the subproblem in the comparator, which is to find if putting key1 or key2 first. The way we can do this is to try putting each of them in front and behind, and then converting them to integers and comparing. Essentially we are solving the subproblem for 2 keys.

Complexity

• Time: $O(nlogn)$
• Space: $O(n)$

Code

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        def custom_compare(key1, key2):
            if int(key1+key2) > int(key2+key1): return -1
            else: return 1
 
        nums = sorted(map(lambda x: str(x), nums), key=cmp_to_key(custom_compare))
        return str(int(''.join(nums)))