Largest Number

Medium
351.

Largest Number

Largest Number is a medium coding problem on arrays, strings and sorting, asked in Amazon, Microsoft, Adobe and Meta interviews.

Given a list of non-negative integers nums, arrange them so that they form the largest possible number, and return it as a string.

Example 1

Input
nums = [10,2]
Output
210

Example 2

Input
nums = [3,30,34,5,9]
Output
9534330

Example 3

Input
nums = [0,0]
Output
0
Explanation
All zeros collapse to a single 0, not 00.

Constraints

  • 1 <= nums.length <= 40
  • 0 <= nums[i] <= 1000000000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {string}
 */
var largestNumber = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Largest Number — Solution in Python, Java & C++

Largest Number solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on arrays and strings.

Largest Number is a medium coding problem on arrays, strings and sorting, asked in Amazon, Microsoft, Adobe and Meta interviews.

Problem statement

Given a list of non-negative integers nums, arrange them so that they form the largest possible number, and return it as a string.

Example 1

Input: nums = [10,2]
Output: 210

Example 2

Input: nums = [3,30,34,5,9]
Output: 9534330

Example 3

Input: nums = [0,0]
Output: 0
Explanation: All zeros collapse to a single 0, not 00.

Constraints

  • 1 <= nums.length <= 40
  • 0 <= nums[i] <= 1000000000

Hints for Largest Number

  1. Hint 1

    Plain numeric or lexicographic sorting both fail: 3 must come before 30, but 30 before 34.

  2. Hint 2

    Compare two numbers a and b by which concatenation is larger — a+b or b+a — and sort by that.

  3. Hint 3

    Watch the all-zeros case: joining gives "000…", which must be reported as "0".

How to solve Largest Number

Sort the numbers as strings with the comparator "a before b iff a + b > b + a", then concatenate.

Approach

  1. Convert to strings.
  2. Sort with the concatenation comparator.
  3. If the first is "0", return "0"; else join.

Why it works

The comparator is a valid total order (it is transitive, which follows from comparing a·10^|b| + b against b·10^|a| + a), and any adjacent pair out of that order could be swapped to increase the result — so the sorted order is maximal.

Complexity

  • Time — O(n log n · L)
  • Space — O(n · L)

Pitfalls

  • Neither numeric nor lexicographic order works (3 vs 30 vs 34).
  • [0, 0] must return "0", not "00".

Reference solution

Python

import functools

def largestNumber(nums) -> str:
    strs = [str(x) for x in nums]
    strs.sort(key=functools.cmp_to_key(lambda a, b: (b + a > a + b) - (b + a < a + b)))
    if strs[0] == "0":
        return "0"
    return "".join(strs)

Java

public static String largestNumber(int[] nums) {
    String[] strs = new String[nums.length];
    for (int i = 0; i < nums.length; i++) strs[i] = String.valueOf(nums[i]);
    Arrays.sort(strs, (a, b) -> (b + a).compareTo(a + b));
    if (strs[0].equals("0")) return "0";
    StringBuilder sb = new StringBuilder();
    for (String x : strs) sb.append(x);
    return sb.toString();
}

C++

string largestNumber(vector<int>& nums) {
    vector<string> strs;
    for (int x : nums) strs.push_back(to_string(x));
    sort(strs.begin(), strs.end(), [](const string& a, const string& b) {
        return a + b > b + a;
    });
    if (strs[0] == "0") return "0";
    string out;
    for (const string& x : strs) out += x;
    return out;
}

JavaScript

var largestNumber = function(nums) {
    const strs = nums.map(function(x) { return String(x); });
    strs.sort(function(a, b) {
        const ab = a + b;
        const ba = b + a;
        if (ba < ab) return -1;
        if (ba > ab) return 1;
        return 0;
    });
    if (strs[0] === "0") return "0";
    return strs.join("");
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings