179. Largest Number
Model: qwen3.5:9b
Topics: Sort
FAANG asked: 1
Acceptance rate: 30.8%
Problem Breakdown
We are given a list of non-negative integers and need to concatenate them in an order that produces the largest possible numerical value when read as a string. Since Python handles arbitrarily large integers, returning the result directly is fine computationally, but standard integer comparison doesn’t apply here because 9 vs 30 isn’t just about magnitude; it’s about concatenation order ("9"+"30" = “930” > "30"+"9" = “309”).
Inputs: A list of non-negative integers. Outputs: A string representing the largest concatenated number. Constraints & Edge Cases:
- Result can exceed 64-bit integer limits (hence return type
str). - Input length up to 100, values up to .
- All zeros case:
[0, 0]must result in"0", not"00".
Intuition
A brute-force approach would try every permutation of the array. With , that’s impossible (). We need a greedy strategy based on sorting.
The core insight is defining a custom comparison rule for two numbers, a and b, converted to strings: we should place a before b if the concatenation "ab" forms a larger number than "ba". If this relation holds consistently (transitivity), standard sort algorithms can arrange them optimally.
Approach
- Convert: Transform all integers in
numsinto their string representations to facilitate easy concatenation during comparison. - Define Comparator: Create a custom comparator function that takes two strings, compares
"a+b"vs"b+a", and returns the appropriate order (descending). - Sort: Use Python’s sort with this custom key (
functools.cmp_to_key). Since we want the largest number first, ifab > ba,ashould come beforeb. - Join & Handle Zeros: Concatenate the sorted strings into a single result string. Check if the resulting string starts with
"0". If so, it implies all elements were zero; return"0"immediately to avoid returning"00...".
Complexity Analysis
- Time Complexity: , where is the number of integers and is the maximum length of a string representation (approx 10 digits). The sorting dominates with , but each comparison takes time proportional to string concatenation/length. Given constraints (), this is negligible overhead compared to standard sort logic, effectively treated as .
- Space Complexity: to store the list of strings and handle sorting buffers in Python’s Timsort implementation.
Solution
import functools
class Solution:
def largestNumber(self, nums):
# Convert all integers to strings for concatenation comparison
str_nums = [str(num) for num in nums]
# Custom comparator logic:
# If a+b > b+a, then 'a' should come before 'b'.
# We want descending order based on this custom rule.
def compare(x, y):
if x + y > y + x:
return -1 # Python sort is ascending; negative means x comes first (higher priority)
elif x + y < y + x:
return 1 # Positive means y should come before x
else:
return 0
# Apply custom sorting using cmp_to_key wrapper for Python 3 compatibility
str_nums.sort(key=functools.cmp_to_key(compare))
# Join the sorted strings to form the result
res = "".join(str_nums)
# Edge case: if largest number starts with '0', all numbers were zero.
return "0" if res[0] == "0" else res
# Example usage (uncomment for testing):
# print(Solution().largestNumber([10, 2])) # Output: "210"
# print(Solution().largestNumber([3, 30, 34, 5, 9])) # Output: "9534330"
Edge Cases Handled
- All Zeros: The code checks if the resulting string starts with
"0"and returns a single"0"instead of multiple zeros (e.g.,["0", "0"]->"0"). - Single Element: Sorting works correctly on lists of length 1; no special logic needed.
- Large Values: Converting to strings handles values up to without integer overflow issues inherent in fixed-width languages, and the return type is explicitly a string as required.