Problem Explanation

Given a list of non-negative integers, the problem is to arrange them in such a way that they form the largest possible number.

For example, given an input of [3,30,34,5,9], the largest possible number that can be formed is 9534330. This results from arranging the numbers in decreasing order of significance. The resulting number may be very large, so the output will be in string format, not an integer.

Solution Approach

The problem can be solved using a sorting function. We start by converting all integer elements in the array into strings. Then we sort the array of strings, but instead of sorting them in the traditional way, we determine the order based on which combination of two numbers will give a larger number.

For instance, consider two numbers, a and b. Instead of determining the order of a and b based on their individual values, we compare the combined string 'ab' and 'ba'. If 'ab' is larger, then a should come before b, otherwise b should come before a. This way of sorting ensures that the final arrangement of numbers will yield the largest possible number.

We illustrate this with an example, given the list [3,30,34,5,9], it will be sorted to ['9', '5', '34', '3', '30'] and the output will be "9534330".

The outline of the algorithm is as follows:

1. Convert the list of integers into a list of strings.
2. Sort the list of strings based on the comparison of combined strings.
3. Join the sorted list into a single string and return it.

Python Solution

1
2python
3class Solution:
4    def largestNumber(self, nums):
5        if not any(map(bool, nums)):
6            return "0"
7        nums = sorted(map(str, nums), key=lambda v: v*3, reverse=True)
8        return "".join(nums)

Java Solution

1
2java
3import java.util.*;
4class Solution {
5    public String largestNumber(int[] nums) {
6        String[] strNums = new String[nums.length];
7        for(int i = 0; i < nums.length; i++){
8            strNums[i] = String.valueOf(nums[i]);
9        }
10        Arrays.sort(strNums, (a, b) -> (b + a).compareTo(a + b));
11        if(strNums[0].charAt(0) == '0') return "0";
12        StringBuilder sb = new StringBuilder();
13        for(String str : strNums){
14            sb.append(str);
15        }
16        return sb.toString();
17    }
18}

Javascript Solution

1
2javascript
3class Solution{
4    largestNumber(nums) {
5        var strNums = nums.map(String);
6        strNums.sort((a, b) => b + a - (a + b));
7        if (strNums[0] == '0') return '0';
8        return strNums.join("");
9    }
10}

C++ solution

1
2cpp
3class Solution {
4    static bool comparator(string a, string b) {
5        return a + b > b + a;
6    }
7public:
8    string largestNumber(vector<int>& nums) {
9        vector<string> arr;
10        for(auto i:nums)
11            arr.push_back(to_string(i));
12        sort(begin(arr), end(arr), comparator);
13        if(arr[0] == "0") return "0";
14        string res;
15        for(auto &s: arr)
16            res+=s;
17        return res;   
18    }
19};

C# Solution

1
2csharp
3public class Solution {
4    public string LargestNumber(int[] nums) {
5        var strArray = nums.Select(num => num.ToString()).ToArray();
6        Array.Sort(strArray, (a, b) => (b + a).CompareTo(a + b));
7        if (strArray[0] == "0") return "0";
8        return string.Join("", strArray);
9    }
10}

These solutions all follow the same approach. They convert the given integers into strings, then they sort in descending order based on the resultant number when two numbers are joined. If the first element in the sorted array is '0', that means all the elements are zero, so it returns '0'. Otherwise, it joins all the elements in the sorted array into one string that makes the largest number and returns it.

Complexity Analysis

For all the given solutions, the time complexity depends on the sorting function. The sorting in all languages is generally O(nlogn). Therefore, the time complexity for this problem is O(nlogn) in Python, Java, Javascript, C++, and C#.

The space complexity is O(n) for all the solutions as we need an extra list to store the string representation of all the numbers.

Wrapping up

The problem can be solved efficiently using a custom sorting function. Although the resulting number can be very large, by returning the result in string form, we can always produce a correct result for any input size within the reasonable constraints of the problem. Despite the potentially large input size, the time complexity remains relatively low because we use a sorting function with a time complexity of O(nlogn).