Largest Number — Solution

Problem

Given a list of non-negative integers, arrange them so that their concatenation forms the largest possible number. The result may be very large, so return it as a string.

• Input: nums = [3, 30, 34, 5, 9]
• Output: "9534330"
• Explanation: concatenating in this order produces the numerically largest string

A counter-example showing the trap: [3, 30] → "330", not "303" — even though 30 > 3 numerically, placing 3 first gives the larger result.

Intuition

The problem reduces to sorting, but not by numeric value. For any two numbers a and b, a should come before b whenever the string a+b is lexicographically greater than b+a. This comparison is transitive (if a beats b and b beats c, then a beats c), so a standard sort with this custom comparator produces the globally optimal arrangement.

Solution — Custom Comparator Sort

Convert each number to a string, then sort using the concatenation comparison. The final edge case is when the largest element after sorting is "0" — that means all inputs are zero, and the result should be a single "0".

1. Convert every integer to its string representation.
2. Sort the string array in descending order using the comparator: a comes before b if a + b > b + a.
3. If the first element after sorting is "0", all inputs were zero — return "0".
4. Otherwise, join all strings and return the result.

1from functools import cmp_to_key
2
3def largestNumber(nums: list[int]) -> str:
4    def compare(num_a: str, num_b: str) -> int:
5        # a before b when a+b forms a larger number than b+a
6        if num_a + num_b > num_b + num_a:
7            return -1  # negative means a sorts first (ascending sort = descending value)
8        elif num_a + num_b < num_b + num_a:
9            return 1
10        return 0
11
12    string_nums = [str(n) for n in nums]
13    string_nums.sort(key=cmp_to_key(compare))
14
15    result = "".join(string_nums)
16    # [0, 0, 0] would produce "000" — collapse to single "0"
17    return "0" if result[0] == "0" else result

Time: O(n log n × k) — n log n comparisons, each comparing two strings of length up to 2k where k is the average digit count.

Space: O(n × k) — storing the string representation of each number.

Complexity Summary

Common Mistakes

• Sorting by numeric value — [3, 30] sorted numerically puts 30 first, yielding "303" instead of the correct "330". Always use the string concatenation comparator.
• Wrong comparator direction in Java — (b + a).compareTo(a + b) places b first when b+a is larger. Swapping the operands reverses the sort and produces the smallest number instead.
• Missing the all-zeros edge case — [0, 0] produces "00" after joining, but the expected output is "0". After sorting, if the first element is "0", return early.
• Comparing concatenated numbers as integers — two 10-digit numbers concatenated form a 20-digit number that overflows even a 64-bit integer. Always compare as strings.
• Using plain lexicographic sort — "9" vs "30" happens to work (since "9" > "3"), but "9" vs "91" breaks it: lexicographically "91" > "9", but "991" > "919" means 9 should come first. The concatenation comparator handles all cases correctly.

Related Problems

• Sort Colors — sorting in-place with custom ordering constraints
• Reorganize String — greedy arrangement of characters to satisfy a global condition
• Remove K Digits — greedy construction of an optimal digit string using a monotone stack
• Top K Frequent Words — custom comparator sort combining numeric and lexicographic criteria