Solution Explanation for Largest Number

The problem requires arranging a list of non-negative integers to form the largest possible number. The challenge lies in correctly comparing numbers to determine their optimal ordering. Simply sorting them numerically won't work because we need to consider the concatenation effect. For example, 3 and 30 should be ordered as 330, not 303.

Approach:

The core idea is to use a custom comparison function within a sorting algorithm. This comparison function determines the order of two numbers based on which concatenation produces a larger number.

Algorithm:

1. Convert to Strings: Convert each integer in the input array nums to its string representation. This allows for easy concatenation during comparison.

2. Custom Comparison: Implement a comparison function (often a lambda function or a separate comparator class) that takes two strings (a and b) as input. This function returns:

   • A positive value if a + b (concatenation) is lexicographically smaller than b + a. This implies b should come before a in the final arrangement.
   • A negative value if a + b is lexicographically larger than b + a. This implies a should come before b.
   • Zero if they are equal.

3. Sort: Use a sorting algorithm (like sort in Python, Java, C++, or sort.Slice in Go) with the custom comparison function to sort the string representations of the numbers.

4. Handle Leading Zeros: After sorting, check if the first element of the sorted array is "0". If it is, it means all the numbers are zeros, and the result should be "0".

5. Concatenate and Return: Join the sorted string representations using an empty string as a separator to create the final largest number string.

Time and Space Complexity:

• Time Complexity: O(N log N), dominated by the sorting algorithm. The comparison function takes O(M) time in the worst case, where M is the maximum length of a number string, but this is usually a small constant factor compared to the sorting time.

• Space Complexity: O(N) to store the string representations of the numbers. In-place sorting algorithms can reduce space usage further, but this is still largely dominated by the N strings themselves.

Code Examples with Explanations:

Python:

from functools import cmp_to_key
 
class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        nums = [str(v) for v in nums]  # Convert to strings
        nums.sort(key=cmp_to_key(lambda a, b: 1 if a + b < b + a else -1)) #Custom Sort
        return "0" if nums[0] == "0" else "".join(nums) #Handle Zeros and Join

The cmp_to_key function is used to adapt the comparison lambda function for the sort method that needs a key function.

Java:

import java.util.*;
 
class Solution {
    public String largestNumber(int[] nums) {
        List<String> vs = new ArrayList<>();
        for (int v : nums) {
            vs.add(String.valueOf(v)); //Convert to String
        }
        vs.sort((a, b) -> (b + a).compareTo(a + b));//Custom Sort using Lambda
        if ("0".equals(vs.get(0))) {
            return "0";
        }
        return String.join("", vs); //Join Strings
    }
}

Java uses a Comparator within the sort method, providing flexibility in sorting behavior.

C++:

#include <algorithm>
#include <string>
#include <vector>
 
class Solution {
public:
    string largestNumber(vector<int>& nums) {
        vector<string> vs;
        for (int v : nums) vs.push_back(to_string(v)); //Convert to String
        sort(vs.begin(), vs.end(), [](string& a, string& b) { //Lambda for Custom Sort
            return a + b > b + a;
        });
        if (vs[0] == "0") return "0"; //Handle Zeros
        string ans;
        for (string v : vs) ans += v; //Join Strings
        return ans;
    }
};
 

C++ uses a lambda function as a custom comparator for sort.

The other languages (Go, C#, TypeScript, JavaScript) follow similar patterns, adapting the core algorithm to their specific syntax and libraries. The key is the custom comparison to correctly order the numbers for the largest possible concatenation.