Largest Number Formed from an Array

Problem Statement

Given a list of non-negative integers, arrange them so that their concatenation forms the largest possible number. Return it as a string.

Example

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

Approach

Convert numbers to strings and sort with a custom rule: a should come before b if a + b > b + a (comparing the two concatenations). After sorting, join them. Handle the all-zeros edge case by returning "0" if the first character is '0'.

Complexity

• Time: O(n log n * k), k = average number length
• Space: O(n)

Solution Code

Python

from functools import cmp_to_key
def largestNumber(nums):
    strs = list(map(str, nums))
    def cmp(a, b):
        if a + b > b + a: return -1
        if a + b < b + a: return 1
        return 0
    strs.sort(key=cmp_to_key(cmp))
    result = "".join(strs)
    return "0" if result[0] == "0" else result

Java

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 s : strs) sb.append(s);
    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 res;
    for (auto& s : strs) res += s;
    return res;
}

Key Takeaways

• The comparator compares concatenations, not the numbers themselves.
• Always handle the all-zeros case to avoid returning "00".
• Reference: LeetCode 179 (Largest Number).