Beats 99% | O(n + k*logk) runtime and O(1) space
Intuition\nSelect the children with the max happiness to maximize the sum of the happiness.\n\n# Approach\nAvoid sorting of the very happy children with happine
# Intuition\nSelect the children with the max happiness to maximize the sum of the happiness.\n\n# Approach\nAvoid sorting of the very happy children with $$happiness > K$$.\nAvoid sorting of the unhappy children. All of them will be zeroed.\n\n# Complexity\n- Time complexity: $$O(n + k*logk)$$ on average\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(1)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    long long maximumHappinessSum(vector<int>& happiness, int k)\n    {\n        // remove n-k smallest children. they are not calculated\n        // runtime O(n) on average\n        nth_element(happiness.begin(), happiness.begin() + k, happiness.end(), greater<>());\n        happiness.resize(k); // runtime O(1)\n        // number of elements is k now\n\n        // divide the rest into 2 groups, when the first group is greater than k.\n        // the first group should not be sorted.\n        // runtime O(k)\n        auto smallIter = partition(happiness.begin(), happiness.end(), [k](int i) {return i >= k;});\n        \n        long long sum = 0;\n\n        // calculate the first group\n        auto iter = happiness.begin();\n        // runtime O(first group) <= O(k)\n        for (int i = 0; iter < smallIter; ++i, ++iter)\n        {\n            sum += *iter - i;\n        }\n\n        // part of the second group will be zeroed at some point.\n        // create max-heap to find the not zeroed ones.\n        // runtime O(second group) <= O(k)\n        make_heap(smallIter, happiness.end());\n\n        // runtime O(non-zeroed in the second group) <= O(k) iterations of O(log(second group))\n        //     ==> O(k*logk)\n        for (int i = smallIter - happiness.begin();\n             i < k\n             && *smallIter > i; // stop when all the rest are zeroed\n             ++i)\n        {\n            sum += *smallIter - i;\n            pop_heap(smallIter, happiness.end()); // O(log(second group)) <= O (logK)\n            happiness.pop_back(); // runtime O(1)\n        }\n\n        return sum;\n    }\n};\n```
['Heap (Priority Queue)', 'C++']