Largest Number

Leetcode Problem:

• Largest Number

Summary

• Given a list of non-negative integers, arrange them to form the largest number and return it as a string.

Approach

• The approach used is to first convert all the numbers into strings, then sort them in descending order based on a custom comparison function
• The comparison function concatenates each pair of strings in both orders (ab and ba) and returns the one that results in the larger number
• After sorting, the strings are concatenated in reverse order to form the largest possible number.

Complexity

• O(n log n) due to the sorting operation, where n is the number of elements in the input list.

Explain

• The solution code first converts all the numbers in the input list into strings
• It then defines a custom comparison function `cmp` that takes two strings `a` and `b` as input
• This function concatenates each pair of strings in both orders (ab and ba) and returns the one that results in the larger number
• The `largestNumber` function then sorts the list of strings using this comparison function and concatenates them in reverse order to form the largest possible number
• Finally, it checks if the resulting number starts with '0' and returns '0' if it does, to handle the case where all the numbers are zeros.

Solution Code:

class Solution {
public:
    static bool cmp(string a, string b){
        string aa = a + b;
        string bb = b + a;
        return aa < bb;
    }
    string largestNumber(vector& nums) {
        vector str_nums;
        for(int i = 0 ; i < nums.size(); i++){
            str_nums.push_back(to_string(nums[i]));
        }
        sort(str_nums.begin(), str_nums.end(), cmp);
        string ans = "";
        for(int i = str_nums.size() - 1; i >= 0 ; i--){
            ans += str_nums[i];
        }
        if (ans.find("0") == 0) return "0";
        return ans;
    }
};