NeetCode #123LC-179MediumArrays & Hashing
← Back to All Problems#123 · #179 · Largest Number(最大数)
📌 Problem Statement & Constraints
Given a list of non-negative integers
nums, arrange them to form the largest possible number and return it as a string. The result may be very large, so return a string rather than an integer. Constraints: 1 <= nums.length <= 100, 0 <= nums[i] <= 10^9.💡 Core Algorithmic Approaches
- Sorting by numeric value is wrong:
9should precede34, but so should34precede3? No -- the correct criterion is a pairwise comparison. - Two numbers
aandbshould be ordered so thatabeforebifa + b(string concatenation) is lexicographically greater thanb + a. - This comparator is a valid total order (it is transitive), so a comparison sort can be used with it.
- Finally, handle the all-zeros case: the joined result would be
"000...", which must be returned as"0".
💻 Benchmark Python3 Implementation
class Solution:
def largestNumber(self, nums: List[int]) -> str:
from functools import cmp_to_key
def cmp(a: str, b: str) -> int:
# a should come first if a+b > b+a lexicographically
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(cmp))
res = "".join(parts)
return "0" if res[0] == "0" else res # all zeros -> "0"⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n log n * L) where L is the maximum number of digits: the comparator performs string concatenations of length up to 2L.
💾 Space Complexity
O(n * L) for the string list and the result.
⚠️ Interview Pitfalls & Follow-ups
- Sorting by numeric value:
[3, 30, 34]would give"34303", but the correct answer is"34330". - Comparing only the first digit: insufficient for multi-digit numbers.
- Forgetting the all-zeros case:
[0, 0]would produce"00", which must be returned as"0". - Returning an integer: the result can exceed 64 bits, so a string is required.
- Assuming the comparator needs to be symmetric: it must return negative/zero/positive, and the direction encodes the ordering.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.