[C++] Custom Comparator O(nlog(n)) | O(n)


The best method is to make a custom comparator that sorts based on whichever is larger after concatenation. (basically lexicographically but a little different)

static bool mycomp(string a, string b)
    // this seems obvious after you see it
    return a+b > b+a;

string Solution::largestNumber(const vector<int> &A) 
    int n = A.size();
    // converting to string once instead of doing it in the comparator.
    vector<string> strA(n);
    for(int i=0; i<n; ++i)
        strA[i] = to_string(A[i]);
    // custom sort
    sort(strA.begin(), strA.end(), mycomp);
    // concatenation
    string ans = "";
    for(auto i : strA)
        ans += i;
    // remove leading 0's
    if(ans[0] == '0') return "0";
    return ans;


This is O(nlogn) solution and not O(n)


Thanks for pointing it out.