Generated by Codex with GPT-5

Quick facts

• Difficulty: MEDIUM
• Problem: Largest Number
• Main tags: Array, String, Greedy, Sorting

What the problem is really asking

The input is a list of non-negative integers. The task is to reorder them so that their decimal representations form the largest possible concatenated number, then return that number as a string.

The important detail is that normal numeric sorting is not enough. For example, 9 should come before 34, but 3 should come after 34 because 343 is larger than 334.

So the problem is really about choosing the right ordering rule between every pair of numbers.

The key insight

For two numbers a and b, there are only two possible relative orders:

• put a before b, giving ab
• put b before a, giving ba

Whichever concatenation is larger tells the correct order for that pair.

For example, compare 3 and 30:

• 330 is larger than 303, so 3 must come before 30

Compare 34 and 3:

• 343 is larger than 334, so 34 must come before 3

This gives a greedy sorting rule: sort numbers as strings, but compare two strings by left + right versus right + left.

How to derive the optimal solution

A brute-force approach would try every permutation, concatenate each one, and keep the largest. That is far too slow because there are n! possible orders.

The way out is to notice that the final answer is built from local pair decisions. If placing x before y gives a larger two-number string than placing y before x, then any globally optimal answer should keep x before y whenever those two numbers are adjacent. Otherwise, swapping them would improve the final concatenation.

That means the problem becomes a custom sort:

1. Convert every number to a string.
2. Sort strings with the comparator x + y > y + x.
3. Join the sorted strings.
4. If the first sorted string is "0", return "0" instead of something like "000".

The all-zero case matters because the largest number formed from [0, 0] is the single string "0", not "00".

Python solution

from functools import cmp_to_key
from typing import List, Sequence


def compare_for_largest_number(left: str, right: str) -> int:
    """
    Order two numeric strings for the largest possible concatenation.

    Python's sort expects:
    - a negative value when left should come before right
    - a positive value when right should come before left
    - zero when either order is equivalent
    """
    left_first = left + right
    right_first = right + left

    if left_first > right_first:
        return -1
    if left_first < right_first:
        return 1
    return 0


def build_largest_number(numbers: Sequence[int]) -> str:
    """Return the largest number that can be formed by reordering numbers."""
    number_strings = [str(number) for number in numbers]

    if not number_strings:
        return "0"

    number_strings.sort(key=cmp_to_key(compare_for_largest_number))

    # If the largest leading value is zero, every value must be zero.
    if number_strings[0] == "0":
        return "0"

    return "".join(number_strings)


class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        return build_largest_number(nums)

Why this works

The comparator directly answers the only question that matters between two candidates: which order makes the combined string larger?

Suppose a final arrangement has adjacent strings x and y, but y + x is larger than x + y. Swapping those two adjacent strings would make the whole final number larger while leaving every other position unchanged. Therefore, an optimal arrangement cannot contain that inverted pair.

Sorting with the rule x + y >= y + x removes those inversions. Once every adjacent pair is in the best relative order, the joined result is the largest possible concatenation.

Let n be the number of integers and k be the maximum number of digits in any integer. Sorting takes O(n log n) comparisons, and each comparison may inspect O(k) characters from the two concatenations. The total time complexity is O(n log n * k). The extra space complexity is O(n * k) for the string versions and the final output.

Interview follow-ups

Why does comparing a + b and b + a produce a valid sort order?

The expected explanation is an exchange argument. If two adjacent strings are in the wrong order, swapping them improves the final concatenated value. Therefore, no optimal answer can contain such an adjacent inversion.

Sorting repeatedly removes those inversions until every pair is locally ordered by the same rule. Because each local improvement makes the whole string no worse, the final sorted arrangement is globally optimal.

The tradeoff is that this is not a normal numeric comparison. The candidate should avoid saying “sort descending” by integer value, because examples like 30 and 3 immediately break that idea.

How should the solution handle inputs like [0, 0, 0]?

After sorting, if the first string is "0", then every other string must also be "0". No positive number could appear after a leading zero under the custom comparator, because any positive string before "0" would produce a larger concatenation.

In that case, the result should be exactly "0". Returning "000" is numerically equivalent, but it violates the expected output format and usually fails LeetCode tests.

This check is O(1) after sorting and does not change the main complexity.

Could this be solved without a comparator?

In some languages or constrained settings, candidates try to sort by repeating each string to a fixed length, such as using key=lambda value: value * 10 in Python. That can work when the maximum number of digits is tightly bounded, but it depends on the constraint and is less general.

The comparator is the more robust interview answer because it directly encodes the mathematical ordering rule. It also avoids explaining why a repetition length is sufficient for the current constraints.

If the interviewer asks for a key-based optimization, the candidate should first state the digit bound, then choose a repetition length that covers it. Without a bound, the comparator is safer.

How would the answer change if the interviewer asked for the smallest number?

The same idea applies, but the comparator is reversed. Instead of placing left before right when left + right is larger, place it first when left + right is smaller.

There is one extra practical issue: if the input contains zeros and positive numbers, the smallest valid number usually should not start with zero unless the problem explicitly allows leading zeros. In that variation, the solution may need to put the smallest non-zero prefix first, then append zeros and the remaining ordered strings according to the exact output rules.

The complexity remains O(n log n * k) because it is still a custom sort over string concatenations.

What if the numbers are extremely large strings instead of integers?

The same comparator works as long as each input string represents a non-negative integer without signs or decimal points. Converting from integer to string is no longer needed, but the ordering rule stays left + right versus right + left.

The main tradeoff becomes comparison cost. Concatenating very large strings inside every comparator call can allocate a lot of temporary memory. A more careful implementation can compare the virtual concatenations character by character without building left + right and right + left.

That optimization keeps the same asymptotic comparison cost, but it can reduce memory churn and improve constant factors for very large inputs.

Practical takeaway

The problem looks like sorting numbers, but it is really sorting string fragments by the value they create when placed next to each other.

The reliable rule is simple: for any two strings x and y, put x first if x + y is larger than y + x. Once that comparator is in place, the rest of the solution is ordinary sorting plus one cleanup check for the all-zero case.