Domain 2MediumCORE

Largest Number

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').

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Sort

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 10910^9.
  • All zeros case: [0, 0] must result in "0", not "00".

Intuition

A brute-force approach would try every permutation of the array. With N=100N=100, that’s impossible (O(N!)O(N!)). 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

  1. Convert: Transform all integers in nums into their string representations to facilitate easy concatenation during comparison.
  2. Define Comparator: Create a custom comparator function that takes two strings, compares "a+b" vs "b+a", and returns the appropriate order (descending).
  3. Sort: Use Python’s sort with this custom key (functools.cmp_to_key). Since we want the largest number first, if ab > ba, a should come before b.
  4. 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: O(Nlog⁡N⋅L)O(N \log N \cdot L), where NN is the number of integers and LL is the maximum length of a string representation (approx 10 digits). The sorting dominates with log⁡N\log N, but each comparison takes time proportional to string concatenation/length. Given constraints (N=100N=100), this is negligible overhead compared to standard sort logic, effectively treated as O(Nlog⁡N)O(N \log N).
  • Space Complexity: O(N)O(N) 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 10910^9 without integer overflow issues inherent in fixed-width languages, and the return type is explicitly a string as required.