Largest Number

Problem Statement

Given a list consisting of non-negative integers named nums, the task is to rearrange these integers to form the largest possible number. This arrangement and subsequent combination need to return a number in a string format due to potential limitations in standard numerical data types for handling very large numbers. In essence, each integer from the list must be treated as a string and concatenated in such an order that it results in the largest combined value.

Examples

Example 1

Input:

nums = [10,2]

Output:

"210"

Example 2

Input:

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

Output:

"9534330"

Constraints

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

Approach and Intuition

To solve the problem of determining the order of elements to form the largest number, let’s delve into some detailed steps and the reasoning behind them:

1. Convert all the numbers in the list to strings. This is necessary because we need to concatenate the numbers, and string manipulation is straightforward for this operation.
2. Sort the array, but not with a typical numerical ordering. The ordering is determined by comparing two numbers (x and y), and seeing which combination forms a higher number when placed together, i.e., comparing xy with yx.
3. For instance, if x = '9' and y = '34', you'd compare '934' and '349' to decide the order in which to place '9' and '34'.
4. Once the array is sorted with this custom rule, concatenate all the elements.
5. A special case arises when the array consists solely of zeros (e.g., [0,0,0]). Here, instead of returning "000", we should return just "0".
6. Handling large numbers: The result can be quite large, which is why the result is returned in string format to avoid overflow issues with standard integer types.

Examples from the constraints demonstrate the application of the sorting logic:

• In example one (nums = [10,2]), the algorithm would determine that placing '2' before '10' in string format ('210') forms a larger number than placing '10' before '2' ('102'). Therefore, the result is "210".
• Similarly, for nums = [3,30,34,5,9], the concatenation that results in the largest number is '9534330', giving the final output as "9534330".

This approach ensures that regardless of the list's size (up to 100 elements) or the individual values (up to 1 billion), we can generate the largest possible number by a methodical assessment of string combinations.

Solutions

class Solution {
public:
    string largestNumber(vector<int>& nums) {
        customSort(nums);
        string maxNum;
        for (int num : nums) {
            maxNum += to_string(num);
        }
        return maxNum[0] == '0' ? "0" : maxNum;
    }
    
private:
    const int CHUNK = 32;
    
    void sortedInsert(vector<int>& nums, int left, int right) {
        for (int i = left + 1; i <= right; ++i) {
            int temp = nums[i];
            int j = i - 1;
            while (j >= left && compareNumbers(temp, nums[j])) {
                nums[j + 1] = nums[j];
                --j;
            }
            nums[j + 1] = temp;
        }
    }
    
    void mergeGroups(vector<int>& nums, int left, int mid, int right) {
        vector<int> leftPart(nums.begin() + left, nums.begin() + mid + 1);
        vector<int> rightPart(nums.begin() + mid + 1, nums.begin() + right + 1);
    
        int i = 0, j = 0, k = left;
        while (i < leftPart.size() && j < rightPart.size()) {
            if (compareNumbers(leftPart[i], rightPart[j])) {
                nums[k++] = leftPart[i++];
            } else {
                nums[k++] = rightPart[j++];
            }
        }
        while (i < leftPart.size()) nums[k++] = leftPart[i++];
        while (j < rightPart.size()) nums[k++] = rightPart[j++];
    }
    
    void customSort(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; i += CHUNK) {
            sortedInsert(nums, i, min(i + CHUNK - 1, n - 1));
        }
        for (int size = CHUNK; size < n; size *= 2) {
            for (int left = 0; left < n; left += 2 * size) {
                int mid = left + size - 1;
                int right = min(left + 2 * size - 1, n - 1);
                if (mid < right) {
                    mergeGroups(nums, left, mid, right);
                }
            }
        }
    }
    
    bool compareNumbers(int x, int y) {
        return to_string(x) + to_string(y) > to_string(y) + to_string(x);
    }
};