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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Largest Number

Number: 179

Difficulty: Medium

Paid? No

Companies: Google, Zoho, Meta, Amazon, Microsoft, Bloomberg, tcs, Myntra, Adobe, Oracle, Accenture, Zalando, Nykaa, Salesforce, Apple, Yahoo, TikTok, Huawei, Works Applications

Problem Description

Given an array of non-negative integers, the goal is to arrange them such that they form the largest possible number. The result is returned as a string since the number can be very large.

Key Insights

  • The order in which numbers appear drastically affects the concatenated result.
  • A custom sorting strategy is required where two numbers are compared by checking which concatenation (first-second vs second-first) yields a larger number.
  • Edge case: When the numbers are all zeros, the result should be "0" instead of several leading zeros.

Space and Time Complexity

Time Complexity: O(n log n * k), where n is the number of elements in the array and k is the maximum number of digits in a number (due to string comparisons in the custom sort). Space Complexity: O(n * k) for storing and processing the strings.

Solution

We solve the problem by converting all integers to strings so that we can use string concatenation to compare the results. A custom comparator is defined that, given two number strings, compares the concatenated results in both orders. By sorting the array using this comparator in descending order, we ensure that placing the highest contributing number first yields the largest possible number. After sorting, a check is performed to return "0" if the highest number is "0". Finally, the sorted strings are concatenated to form the answer.

Code Solutions

# Import cmp_to_key to convert a comparator function to a key function for sorting
from functools import cmp_to_key

# Define the comparator function
def compare(x, y):
    # Compare two possible orders: x+y and y+x
    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   # both orders are equal

def largestNumber(nums):
    # Convert all integers to strings
    nums_str = list(map(str, nums))
    # Sort the strings using the custom comparator
    nums_str.sort(key=cmp_to_key(compare))
    # If the largest number is '0', the entire number is 0 so return '0'
    if nums_str[0] == "0":
        return "0"
    # Concatenate the sorted numbers and return the result
    return "".join(nums_str)

# Example usage:
print(largestNumber([3, 30, 34, 5, 9]))  # Output: "9534330"
← Back to All Questions