⚡Flashcard Drill➔
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

  1. Sorting by numeric value is wrong: 9 should precede 34, but so should 34 precede 3? No -- the correct criterion is a pairwise comparison.
  2. Two numbers a and b should be ordered so that a before b if a + b (string concatenation) is lexicographically greater than b + a.
  3. This comparator is a valid total order (it is transitive), so a comparison sort can be used with it.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems