SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

Given a list of non-negative integers, the task is to arrange them such that they form the largest possible number. The output should be the largest number represented as a string. For example, given the input [3, 30, 34, 5, 9], the largest possible number is "9534330".

Intuition

The problem requires us to sort numbers in a non-standard way. Instead of sorting by value, we need to sort based on the most significant digits when the numbers are concatenated together. The main idea is to determine the order of two numbers by comparing their possible concatenations. If placing one number before another yields a larger concatenated result, that order should be preferred.

Approach

1. Convert Numbers to Strings:

   • Since concatenation and comparison are easier with strings, start by converting each number in the list to its string representation.

2. Custom Sort:

   • Sort the list of string numbers using a custom comparator. For two strings a and b, compare a + b and b + a. If a + b is larger, a should come before b; otherwise, b should come before a.

3. Edge Case:

   • If the largest number after sorting is "0", the result should be "0" to handle cases where the input list consists of only zeros.

4. Concatenate and Return:

   • Finally, concatenate all the numbers in the sorted list to form the largest number and return it as a string.

Complexity

Time Complexity:

O(n log n), where n is the number of integers in the input list. The complexity is dominated by the sorting operation, which uses a custom comparator that runs in constant time.

Space Complexity:

O(n), where n is the number of integers in the input list. This space is used for storing the string representations of the numbers and the final result.

Code

C++

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

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

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

        string result;
        for (string &numStr : numStrs) {
            result += numStr;
        }

        return result;
    }
};

Python

class Solution:
    def largestNumber(self, nums: list[int]) -> str:
        numStrs = [str(num) for num in nums]
        
        def compare(a, b):
            return 1 if a + b < b + a else -1
        
        numStrs.sort(key=cmp_to_key(compare))
        
        if numStrs[0] == "0":
            return "0"
        
        return "".join(numStrs)

Java

class Solution {
    public String largestNumber(int[] nums) {
        String[] numStrs = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            numStrs[i] = String.valueOf(nums[i]);
        }

        Arrays.sort(numStrs, new Comparator<String>() {
            public int compare(String a, String b) {
                return (b + a).compareTo(a + b);
            }
        });

        if (numStrs[0].equals("0")) {
            return "0";
        }

        StringBuilder result = new StringBuilder();
        for (String numStr : numStrs) {
            result.append(numStr);
        }

        return result.toString();
    }
}

JavaScript

/**
 * @param {number[]} nums
 * @return {string}
 */
var largestNumber = function(nums) {
    
    nums.sort((a,b)=>{
        let sa = a.toString()
        let sb = b.toString()
        return parseInt(sa + sb) > parseInt(sb + sa) ? -1 : 1
    })
    if(nums[0] === 0) return '0'
    
    return nums.join('')
};