179. Largest Number
On LeetCode ->Problem¶
Arrange non-negative integers so their concatenation is maximal, then return it as a string.
Key trick¶
For strings a and b, place a first exactly when concatenating a + b produces a larger string than b + a.
Trap¶
- Numeric or lexicographic descending order is insufficient.
- Prefixes require comparing both concatenations, not only the remaining suffix.
- An all-zero input must return
"0", not multiple zeros. - A comparator must return zero for equivalent elements.
Why is it interesting?¶
It turns a global arrangement problem into a custom pairwise sorting rule.
Python solution¶
from functools import cmp_to_key
class Solution:
def largestNumber(self, nums: list[int]) -> str:
def compare(a: str, b: str) -> int:
# Put a before b when a + b forms the larger concatenation.
if a + b > b + a:
return -1
if a + b < b + a:
return 1
return 0
parts = sorted(map(str, nums), key=cmp_to_key(compare))
result = "".join(parts)
# Collapse results such as "000" into "0".
return "0" if result[0] == "0" else result
Sorting takes \(O(n \log n)\) comparisons; each comparison costs up to \(O(k)\) for maximum digit length \(k\).
Comment on my solution¶
The exploration correctly identifies that ordinary string sorting fails and that a custom comparator is needed.
The comparator is too specialized: prefix-plus-zero handling covers cases such as 200 versus 2, but the correct order for every pair depends on comparing their two complete concatenations. The fallback lexicographic comparison therefore fails for 111311 versus 1113.
It also never returns zero when two values are equivalent, which violates the comparator contract, and it does not collapse an all-zero result into "0".
from functools import cmp_to_key
# WRONG
# Wrong Answer: 192/236 testcases passed
# [111311,1113]
# Output: "1113111113"
# Expected: "1113111311"
class Solution:
def largestNumber(self, nums: list[int]) -> str:
# [10,2] -> "210"
# [3,30,34,5,9] -> "9534330"
# - trying all arrangements and keeping the largest is expensive
# - sorting descending all number seen as string
# - 9 > 5 > 34 > 3 > 30 ???
# sorted(["90", "50"], reverse=True) # ['90', '50']
# sorted(["3","30","34","5","9"], reverse=True)
# # ['9', '5', '34', '30', '3']
# 3 should comes before 30
# - maybe separating numbers endings with zeros and other:
# - wrong: [200,1] -> 2001 (not 1200)
# - greedy??
# - count number of digits of the built number
# - [10,2] -> 3
# - [3,30,34,5,9] -> 7
# - then pick best number to build the most significant digit
# - and repeat till the lowest one
# - only problem in sorting is when
# - [200,1] -> 2001
# - [200,2] -> 2200
# - but sorted(["200","2"], reverse=True) # ['200', '2']
# - [22200,222] -> 22200222
# - but sorted(["22200","222"], reverse=True) # ['22200', '222'] but we want 222 > 22200
# - maybe we can write a comparison function that take this
# case into account
def cmp_int(a: str, b: str):
# a="22200", b="222" -> -1 (meaning "22200" is inferior to "222")
if a.startswith(b) and a[len(b):] == "0" * (len(a) - len(b)):
return -1
# conversaly
if b.startswith(a) and b[len(a):] == "0" * (len(b) - len(a)):
return 1
# base case
return -1 if a < b else 1
nums_as_str = [str(n) for n in nums]
nums_as_str.sort(key=cmp_to_key(cmp_int), reverse=True)
return "".join(nums_as_str)