Bucket and sort (O(nlogn)) solution with explanation (might be fast for uniformly distributed integers)


  • 0
    V

    The main idea of sorting based on string comparisons is inspired by many others in this forum who have shared their solutions. But the improvements my solution provides is in string-based sorting only on bucketed values.

    The key idea is that any number beginning with a digit i should come before another number beginning with a digit j for all 0<=(i,j)<=9 and i>j. String-based sorting is needed only for i=j. So, I first sort the numbers based on their most significant digit (MSD), string-sort within each bucket, and append the numbers greedily in decreasing order of the MSD.

    This solution takes 3ms on the all the test cases (similar to other submitted solutions). But, I suspect that if the input is extremely large and the numbers are evenly distributed over the MSDs, this solution might start outperforming other solutions that use "full-sorting".

    class Solution {
    public:
        string largestNumber(vector<int>& nums) {
            if(nums.size() == 0) return "";
            
            // Bucket of size 10 for each of the 10 digits (0-9)
            vector<vector<string>> M(10); 
            for(int i=0; i<nums.size(); i++){
                int key=0;
                int n = nums[i];
                // Get the most significant digit
                while(n != 0){
                    key = n%10;
                    n = n/10;
                }
                // Add number to the bucket indexed by the most significant digit
                M[key].push_back(to_string(nums[i]));
            }
            
            string res="";
            for(int k=9; k>0; k--){ // Numbers with greater MSD should go before numbers with smaller MSD
                if(M[k].size() == 0) continue;
                // Sort within the bucket
                sort(M[k].begin(), M[k].end(), [&](string& s1, string& s2) { return s1+s2 > s2+s1; } );
    
                for(int j=0; j<M[k].size(); j++) res += M[k][j];
            }
    
            // Append 0's only if the result has prefix numbers
            if(res.length()>0){
                for(int j=0; j<M[0].size(); j++) res += M[0][j];
            }
            else if(M[0].size() > 0){
                res = "0";   // else just output "0"
            }
    
            return res;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.