179.Largest_Number(Medium).md

179. Largest Number (Medium)

Date and Time: Sep 27, 2024, 22:54 (EST)

Link: https://leetcode.com/problems/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"

Constraints:

• 1 <= nums.length <= 100

• 0 <= nums[i] <= 10^9

Walk-through:

1. Convert each element from nums into str.

2. sort nums by the function we define, if n1 + n2 > n2 + n1, we return -1, so it will sort n1 in front. Else, we return 1 and make n2 in front. Each time we only compare two words from nums, and then it also compares previous elements to sort these two words.

3. Finally, "".join(nums) and convert it to str to return.

Python Solution:

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        # convert element into str
        for i, n in enumerate(nums):
            nums[i] = str(n)
        
        def compare(n1, n2):
            if n1 + n2 > n2 + n1:
                return -1
            else:
                return 1
        
        nums = sorted(nums, key=cmp_to_key(compare))
        return str(int("".join(nums)))

Time Complexity: $O(nlog\ n)$, n is the length of nums, because we sort nums.
Space Complexity: $O(1)$