We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Largest Number

Difficulty: Medium

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.

Key Insights

  • The order of concatenation of numbers affects the resulting value.
  • To determine the correct order, we can compare the concatenated results of pairs of numbers in both possible orders.
  • A custom sorting approach is necessary to rearrange the numbers optimally.
  • The largest number may start with '0' if all numbers are zeros, so we need to handle that case.

Space and Time Complexity

Time Complexity: O(n log n), where n is the number of elements in the input list, due to the sorting process.
Space Complexity: O(n), for storing the sorted elements.

Solution

To solve the problem, we will use a custom sorting mechanism based on the concatenation of the numbers. Specifically, we will define a comparison function that compares two numbers by comparing the two possible concatenated results. We can use Python's built-in sorting function with a custom comparator to achieve this. After sorting, we will concatenate the numbers to form the final result.

Code Solutions

from functools import cmp_to_key

def largestNumber(nums):
    # Custom comparator for sorting
    def compare(x, y):
        # Compare concatenated results
        if x + y > y + x:
            return -1  # x should come before y
        elif x + y < y + x:
            return 1   # y should come before x
        else:
            return 0   # equal
    
    # Convert numbers to strings for comparison
    nums_str = list(map(str, nums))
    # Sort using the custom comparator
    nums_str.sort(key=cmp_to_key(compare))
    
    # Edge case: if the largest number is '0', return '0'
    if nums_str[0] == '0':
        return '0'
    
    # Join sorted numbers to form the largest number
    return ''.join(nums_str)
← Back to All Questions