Largest Number

Most sorts in interviews sort by something obvious — a number, a length, an end time. In Largest Number, the order itself is the problem. Numeric order fails, string order fails, and the right rule compares two pieces by trying them both ways.

It is also a lesson in trusting a comparator. A sort only works if "comes before" is consistent, and this one needs a short argument. Having that argument ready is what separates a memorised answer from an understood one.

The problem

Given a list of non-negative integers, arrange them so that writing them one after another forms the largest possible number. Return it as a string, because it can be too long for any integer type.

• [4, 42, 45, 9, 403] → "945442403". The order is 9, 45, 4, 42, 403.
• [0, 0] → "0", not "00".

Constraints: 1 ≤ n ≤ 100, and each value is between 0 and 10⁹.

Clarifying questions

• Return a string? Yes.
• Can values be 0? Yes, and if every value is 0 the answer is "0".
• Negative values? No.
• Can I reorder the input freely? Yes, any order.

Approach 1: the simple way

Try every order and keep the largest string.

1from itertools import permutations234def largest_number_brute(nums: list[int]) -> str:5    """Try every order."""6    best = max("".join(p) for p in permutations(map(str, nums)))7    return "0" if best[0] == "0" else best

Comparing the joined strings directly works because every order has the same total length, so the larger string is the larger number. But there are n! orders: 100! has 158 digits. Even n = 12 is 479 million orders.

The obvious fixes do not work either. Sorting numerically from largest gives 403, 45, 42, 9, 4 → "403454294". Sorting as strings from largest gives "9", "45", "42", "403", "4" → "945424034". Both are smaller than "945442403". The trouble is values that share a prefix: 4 and 42, 4 and 403.

The key insight

You cannot decide where 4 goes by looking at 4 alone. But you can always decide between two pieces: put them side by side both ways and keep the bigger.

Why is a pairwise rule enough? It is an exchange argument, like in greedy problems. In any arrangement, if two neighbours a, b have b + a bigger than a + b, swapping them makes the whole number bigger — everything before and after stays the same, and the two-piece middle grows. So the best arrangement has no such pair, which means it is sorted by this rule.

Is this rule safe to sort with? A sort needs "comes before" to be transitive. Here is why it is. Comparing the strings a + b and b + a (same length) is comparing the numbers a × 10^len(b) + b and b × 10^len(a) + a. Rearranged, that is comparing a / (10^len(a) − 1) with b / (10^len(b) − 1). And a / (10^len(a) − 1) is simply the repeating decimal 0.aaaa… — for 42 it is 0.424242…, for 4 it is 0.4444…. So the rule is "compare the repeating decimals" — a comparison of ordinary numbers, which is always transitive.

Approach 2: optimised — sort with the pairwise rule

1from functools import cmp_to_key234def largest_number(nums: list[int]) -> str:5    """Put a before b whenever a + b beats b + a as a string."""6    def before(a: str, b: str) -> int:7        if a + b > b + a:8            return -1                  # a goes first9        if a + b < b + a:10            return 1                   # b goes first11        return 01213    parts = sorted(map(str, nums), key=cmp_to_key(before))14    result = "".join(parts)15    return "0" if result[0] == "0" else result     # [0, 0] must give "0"

1. Turn the numbers into strings once.
2. Python's sort takes a key, not a comparator; cmp_to_key wraps a two-argument function that returns negative for "a first", positive for "b first", 0 for a tie.
3. Join. If the first piece is "0", every piece is 0 — the biggest piece came first — so return "0".

Dry run on [4, 42, 45, 9, 403]: the rule places 9 first (9 + anything starts with 9), then 45 before 4 (454 beats 445), then 4 before 42 (442 beats 424), then 42 before 403 (42403 beats 40342). Sorted: ["9", "45", "4", "42", "403"], joined "945442403".

Complexity: O(n log n) comparisons, and each comparison builds two strings of up to 2L characters, where L is the longest number (10 digits here). So O(L × n log n) time and O(n × L) space for the strings.

Approach 3: the same order as a plain key

The proof hands you a key function: sort by the repeating decimal 0.aaaa…, largest first. Fraction keeps it exact.

1from fractions import Fraction234def largest_number_key(nums: list[int]) -> str:5    """Same order, from a plain key: a / (10^len(a) - 1), largest first."""6    parts = sorted(map(str, nums),7                   key=lambda s: Fraction(int(s), 10 ** len(s) - 1),8                   reverse=True)9    result = "".join(parts)10    return "0" if result[0] == "0" else result

The keys are 9/9 = 1, 45/99 = 0.4545…, 4/9 = 0.444…, 42/99 = 0.4242…, 403/999 = 0.403403… — the same order. It is the same O(n log n) sort, and it computes each key once instead of building strings in every comparison. Mention it as the proof made executable; lead with the comparator, which interviewers expect. All three versions agreed on 500 random inputs.

Edge cases

• All zeros, [0, 0]: joined "00", fixed to "0".
• One value, [0] → "0"; [7] → "7".
• A value that is a prefix of another, [121, 12]: 12121 beats 12112, so "12121".
• Zero with others, [10, 2]: 210 beats 102, so "210".

Follow-ups

• Smallest number instead? Reverse the rule: a first when a + b is smaller. Leading zeros then need stripping rather than the all-zero check.
• Why not a key like s * 10? Repeating each string to a fixed length does work for bounded lengths, but it needs its own argument about how far to repeat. The fraction key is exact and easy to justify.
• In Java or C++? Pass the comparator directly: (a, b) -> (b + a).compareTo(a + b).