Largest Number — Editorial

Opening the reading…

Intuitionwhy concatenation decides the order

You are not sorting the integers by their numeric values. The important question is what happens when two number strings stand next to each other. If a comes before b, the combined number is a + b; if b comes first, it is b + a. Whichever concatenation is larger tells you which string should occupy the earlier position in the final answer.

For example, 3 must come before 30 because 330 is larger than 303. This rule also handles different digit lengths, where ordinary numeric sorting fails. Sort every string using the rule a + b > b + a, then concatenate the sorted strings. The only exceptional-looking result is an input containing only zeros: its concatenation may be 000, but the required number is simply 0.

The pairwise order is determined by the two possible concatenations.

Approachturning the definition into a custom sort

Convert every integer to a string, because the answer can exceed integer ranges and the comparator needs to concatenate digit sequences directly; keeping integers would risk overflow when forming the comparison.

Sort the strings with a comparator that places a before b when a + b is greater than b + a, because that local choice directly selects the better order for this pair.

Let the sorting algorithm apply that comparator to all pairs, because the comparator defines the global order in which the final concatenation is maximal.

Concatenate the sorted strings from left to right, because every earlier string has already been chosen to contribute the larger possible prefix against the strings after it.

If the first sorted string is 0, return 0 instead of the full concatenation, because the comparator places every zero together but cannot remove repeated zero digits by itself.

Otherwise return the complete concatenation, which is the requested largest number represented as text rather than as an integer.

Complexitythe cost of comparing digit strings

MEASURE	BOUND	WHY
Time	O(n log n x L)	Sorting performs O(n log n) comparisons, and each comparison creates or examines concatenations whose length is at most 2L. The final pass appends n strings and is O(nL), which is covered by the sorting bound for n at least 1.
Space	O(nL) extra	The converted strings occupy O(nL) working space, while the sorting recursion or bookkeeping adds at most O(log n). The returned concatenation is output storage and is excluded. The bound is largest when all n values have close to L digits; with these constraints, L is at most 10.

Here n is the number of input values and L is the maximum number of digits in any converted value. The output string is required output and is excluded from the extra-space bound.

Annotated solutionC++ · custom comparator · complete judge-ready implementation

CPPConvert, sort by concatenation order, normalize an all-zero result, and join the strings.

#include <algorithm>
#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    string largestNumber(vector<int>& nums) {
        vector<string> strs;
        for (int num : nums) {
            strs.push_back(to_string(num));
        }

        sort(strs.begin(), strs.end(), [](const string& a, const string& b) {
            return a + b > b + a;
        });

        if (strs[0] == "0") {
            return "0";
        }

        string ans;
        for (const string& s : strs) {
            ans += s;
        }
        return ans;
    }
};

The comparator is the central line: a + b > b + a means a belongs before b whenever that arrangement creates the larger two-item number. Sorting uses this rule repeatedly, so the resulting sequence puts the strongest possible prefix first at every comparison. The zero check comes after sorting because the first string is then guaranteed to be the largest candidate; if it is 0, every input value must also be zero.