Largest Number

You are given a list of non-negative integers nums. Arrange them in some order and write them one after another, with no separators, to form a single number. For example, the order [34, 5] produces 345 and the order [5, 34] produces 534.

Return the largest number that can be produced this way. Because it can be far too long for any integer type, return it as a string. The result must not have leading zeros, so if every possible arrangement is made only of zeros, return "0".

Example 1

Example 2

Example 3

Constraints

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 109

Pattern Path · Intervals & Greedy · problem 115 of 169

Start simple

Try every permutation, concatenate, and keep the largest: O(n!·L) time for n numbers of total length L.

The key idea

Decide the order one pair at a time. For two numbers written as strings a and b, the only two ways to place them next to each other are a+b and b+a. Both have the same length, so comparing them as strings tells you which order is better for that pair.

Sort with the rule "a goes first if a+b > b+a". This comparison is consistent (it is transitive), so sorting produces a single global order. In that order no adjacent pair can be swapped to make the number bigger, and an exchange argument shows that any arrangement that disagrees with it can be improved by such a swap. So the sorted order is optimal.

The comparator is what makes cases like 3 vs 30 work: 330 > 303, so 3 goes first even though 30 is larger and also beats 3 in plain string order.

Finally, if the first element after sorting is "0", every element is zero, so return "0" instead of a run of zeros.

Complexity

• Time: O(n log n · d), d = digits per number
• Space: O(n · d)

Python

from functools import cmp_to_key

class Solution:
    def largestNumber(self, nums):
        strs = [str(x) for x in nums]

        def compare(a, b):
            # Negative means "a goes first": choose the order whose concatenation is larger.
            if a + b > b + a:
                return -1
            if a + b < b + a:
                return 1
            return 0

        strs.sort(key=cmp_to_key(compare))
        if strs[0] == "0":          # the largest piece is 0, so every piece is 0
            return "0"
        return "".join(strs)

JavaScript

var largestNumber = function(nums) {
  const strs = nums.map(String);
  // a goes before b when a+b forms the larger string (both have equal length).
  strs.sort((a, b) => {
    const ab = a + b, ba = b + a;
    if (ab > ba) return -1;
    if (ab < ba) return 1;
    return 0;
  });
  if (strs[0] === "0") return "0";   // the largest piece is 0, so every piece is 0
  return strs.join("");
};

What the interviewer is checking

It tests whether you can design a custom comparator, justify that it gives a correct total order, and catch the all-zero edge case.

Mistakes to avoid

• Sorting strings in reverse lexicographic order, which wrongly puts 30 before 3.
• Returning "000" for an input of all zeros.
• Converting the result to an integer, which overflows or loses precision for long answers.
• Writing a comparator that returns a boolean where the language expects a negative/zero/positive number (JavaScript, Python cmp_to_key).

Follow-ups to expect

• How would you build the smallest number instead? (Flip the comparator, strip zeros.)
• Why is the comparator transitive? (Concatenation compares like a/(10^len-1) values.)
• Can you avoid building strings? (Compare using digit counts and arithmetic.)

In real software

Custom sort keys built from pairwise rules appear in ranking feeds, ordering version strings and building canonical identifiers from parts.

Practice next