Sort->partial_sort->maxHeap->radix Sort||82ms Beats 99.98%
Intuition\n Describe your first thoughts on how to solve this problem. \nSeveral months ago, this question is solved by Greedy with max heap which is similar to
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nSeveral months ago, this question is solved by Greedy with max heap which is similar to 1 of solution in editoial.\nPut some more approaches in different ways; otherwise there is no need to post my solutions. For what? Against so heavy competitions promoted by many fake accounts? That will be a joke.\n\n4th method uses radix sort with 512 buckets which is the fastest one\n# Approach\n<!-- Describe your approach to solving the problem. -->\nFind the k largest elements using a Greedy algorithm\n1. Method 1 uses std::sort in default ordering which is much faster than sort with the reverse ordering.\n2. Method 2 uses partial_sort (C++20). The TC is reduced, but time not.\n3. Method 3 uses heap(priority_queue) which outperforms the std::sort with reverse ordering but slower than std::sort in default ordering\n4. Method 4 uses radix sort which is the fastest one.\n5. Python 1-line code is provided using sorted function with reverse=True.\nFor comparision the performance of C++ codes are listed in the following table\n\n|Method|Elapsed time|Beats|Memory|\n|---|---|---|---|\n|sort+reverse order|187ms|26.73%|108.92MB|\n|sort+ascending order|98ms|99.63%|107.18MB|\n|partial sort|158ms|67.75%|107.09MB|\n|priority_queue(max heap)|128ms|98.92%|111.30MB|\n|radix sort|82ms|99.98%|133.60MB|\n# Remark \nThe C++ sort are optimized for the default ordering; using reverse order the elapsed time is almost the twice. priority_queue method has less TC but is not so fast like sort+ascending order. The method using radix sort needs the most memory, say probably 30%  more; that is a trade-off between space & time.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(k+n\\log n)\\to O(n+k\\log(n))$$\nradix sort: $O(n+k+512)$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\nradix sort: $O(512)$\n# C++ using std::sort in default ordering||98ms Beats 99.63%\n```\n#pragma GCC optimize("O3", "unroll-loops")\nclass Solution {\npublic:\n    long long maximumHappinessSum(vector<int>& happiness, int k) {\n        const int n=happiness.size();\n        sort( happiness.begin(), happiness.end());\n        \n        long long sum=0;\n        for(int i=0; i<k; i++){\n            long long x=max(0, happiness[n-1-i]-i);\n        //    cout<<x<<endl;\n            sum+=x;\n        }\n            \n        return sum;\n        \n    }\n};\n\n```\n# Code using partial_sort\n```\n#pragma GCC optimize("O3", "unroll-loops")\nclass Solution {\npublic:\n    long long maximumHappinessSum(vector<int>& happiness, int k) {\n        const int n=happiness.size();\n        partial_sort( happiness.begin(), happiness.begin()+k, happiness.end(), greater<>());\n        \n        long long sum=0;\n        for(int i=0; i<k; i++){\n            long long x=max(0, happiness[i]-i);\n        //    cout<<x<<endl;\n            sum+=x;\n        }\n            \n        return sum;\n        \n    }\n};\n\n```\n# Code using priority_queue||128ms Beats 98.92%\n```\n#pragma GCC optimize("O3", "unroll-loops")\nclass Solution {\npublic:\n    long long maximumHappinessSum(vector<int>& happiness, int k) {\n        int n=happiness.size();\n        priority_queue<int> pq(happiness.begin(), happiness.end());//maxheap\n        long long sum=0;\n        for(int i=0; i<k; i++){\n            long long x=max(0, pq.top()-i);\n        //    cout<<x<<endl;\n            pq.pop();\n            sum+=x;\n        }\n            \n        return sum;\n        \n    }\n};\n\n```\n# C++ using radix sort|82ms Beats 99.98%\n```\n#pragma GCC optimize("O3", "unroll-loops")\nclass Solution {\npublic:\n    vector<int> bucket[512];\n    void radix_sort(vector<int>& nums) {\n        // 1st round\n        for (int x : nums)\n            bucket[x&511].push_back(x);\n        int i = 0;\n        for (auto &B : bucket) {\n            for (auto v : B)\n                nums[i++] = v;\n            B.clear();\n        }\n        // 2nd round\n        for (int x : nums)\n            bucket[(x>>9)&511].push_back(x);\n        i=0;\n        for (auto &B : bucket) {\n            for (auto v : B)\n                nums[i++] = v;\n            B.clear();\n        }\n        // 3rd round\n        for (int x : nums)\n            bucket[x>>18].push_back(x);\n        i=0;\n        for (auto &B : bucket) {\n            for (auto v : B)\n                nums[i++] = v;\n        //    B.clear();\n        }\n    }\n    long long maximumHappinessSum(vector<int>& happiness, int k) {\n        const int n=happiness.size();\n        radix_sort( happiness);\n        \n        long long sum=0;\n        for(int i=0; i<k; i++){\n            long long x=max(0, happiness[n-1-i]-i);\n        //    cout<<x<<endl;\n            sum+=x;\n        }\n            \n        return sum;\n        \n    }\n};\n\n\nauto init = []() {\n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n```\n# Python 1-liner using sorted with reverse=True\n```\nclass Solution:\n    def maximumHappinessSum(self, h: List[int], k: int) -> int:\n        return sum(max(0, x - i) for i, x in enumerate(sorted(h, reverse=True)[:k]))\n\n```\n
['Greedy', 'Sorting', 'Heap (Priority Queue)', 'C++', 'Python3']