LeetCode 179: Largest Number

Problem Description

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⁹

Difficulty: Medium

Tags: array, string, greedy, sorting

Rating: 92.24%

Solution

Here’s my Python solution to this problem:

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        nums = [str(num) for num in nums]
    
        def compare(n1, n2):
            # If n1+n2 is greater than n2+n1, n1 should come first
            if n1 + n2 > n2 + n1:
                return -1
            return 1
        
        # Sort using custom comparison
        nums.sort(key=functools.cmp_to_key(compare))
        
        # Handle edge case of all zeros
        if nums[0] == '0':
            return '0'
        
        return ''.join(nums)

Complexity Analysis

The solution has the following complexity characteristics:

Time Complexity: $O(n)$
Space Complexity: $O(n)$

Note: This is an automated analysis and may not capture all edge cases or specific algorithmic optimizations.