Problem Description

Given a list of non-negative integers nums, arrange them such that they form the largest possible number when concatenated together. The result should be returned as a string, since the largest number may not fit within the range of a 32-bit integer.

• You must arrange the elements of nums in any order to get the largest concatenated number.
• Each element from nums must be used exactly once and not reused.
• If the result is multiple leading zeroes (e.g., "00"), return just "0".

Constraints:

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

Thought Process

At first glance, this problem may seem like a simple sorting task. However, the twist is that the standard numerical or lexicographical order does not yield the largest concatenated number. For example, with nums = [3, 30, 34, 5, 9], sorting numerically or as strings won't work.

The key insight is to compare pairs of numbers by their possible concatenations: for numbers a and b, we need to decide whether ab or ba forms a larger number. This leads us to design a custom sorting rule based on string comparison of these concatenations.

A brute-force approach would consider all permutations, but that is computationally infeasible for large arrays. Instead, we optimize by sorting with a custom comparator.

Solution Approach

• Step 1: Convert all numbers to strings. This is necessary because we will be concatenating them for comparison.
• Step 2: Sort the string numbers using a custom comparator:
  • For two numbers a and b, compare a + b and b + a.
  • If a + b is larger, a should come before b.
• Step 3: Join the sorted array into a single string.
• Step 4: Handle the edge case where the result has leading zeros. If the first character is '0', the entire result is zero, so return "0".

This approach ensures that at each step, the choice made is optimal for the overall largest number.

Example Walkthrough

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

1. Convert to strings: ["3", "30", "34", "5", "9"]
2. Sort with custom comparator:
   • Compare "9" and "5": "95" > "59" ⇒ "9" before "5"
   • Compare "5" and "34": "534" > "345" ⇒ "5" before "34"
   • Compare "34" and "3": "343" > "334" ⇒ "34" before "3"
   • Compare "3" and "30": "330" > "303" ⇒ "3" before "30"

   After sorting: ["9", "5", "34", "3", "30"]

3. Join: "9534330"
4. No leading zeros, so return "9534330"

Time and Space Complexity

• Brute-force approach: Try all permutations (n!), which is infeasible for n up to 100.
• Optimized approach:
  • Sorting takes O(n log n) time, where n is the length of nums.
  • Each comparison involves string concatenation, which is O(k), where k is the max number of digits (up to 10).
  • Overall time complexity: O(n log n * k).
  • Space complexity: O(n * k) for the string representations and result.

Summary

The largest number problem is elegantly solved by recognizing that string concatenation order determines the result, not numerical order. By converting numbers to strings and sorting with a custom comparator based on which concatenation yields a larger value, we efficiently build the largest possible number. Handling the edge case of all zeros ensures correctness. This approach transforms a potentially brute-force problem into a clever greedy algorithm using sorting.

Code Implementation

from functools import cmp_to_key

class Solution:
    def largestNumber(self, nums):
        def compare(a, b):
            if a + b > b + a:
                return -1
            elif a + b < b + a:
                return 1
            else:
                return 0

        as_strs = list(map(str, nums))
        as_strs.sort(key=cmp_to_key(compare))
        result = ''.join(as_strs)
        return '0' if result[0] == '0' else result
      

#include <vector>
#include <string>
#include <algorithm>
using namespace std;

class Solution {
public:
    static bool compare(const string &a, const string &b) {
        return a + b > b + a;
    }

    string largestNumber(vector<int>& nums) {
        vector<string> as_strs;
        for (int num : nums) {
            as_strs.push_back(to_string(num));
        }
        sort(as_strs.begin(), as_strs.end(), compare);
        string result;
        for (const string &s : as_strs) {
            result += s;
        }
        // Remove leading zeros
        if (result[0] == '0') return "0";
        return result;
    }
};
      

import java.util.*;

class Solution {
    public String largestNumber(int[] nums) {
        String[] asStrs = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            asStrs[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(asStrs, new Comparator<String>() {
            public int compare(String a, String b) {
                String order1 = a + b;
                String order2 = b + a;
                return order2.compareTo(order1);
            }
        });
        if (asStrs[0].equals("0")) return "0";
        StringBuilder sb = new StringBuilder();
        for (String s : asStrs) sb.append(s);
        return sb.toString();
    }
}
      

/**
 * @param {number[]} nums
 * @return {string}
 */
var largestNumber = function(nums) {
    let asStrs = nums.map(String);
    asStrs.sort((a, b) => (b + a).localeCompare(a + b));
    let result = asStrs.join('');
    return result[0] === '0' ? '0' : result;
};