✅ Beat 100% | ✨ O(N + k log k) | 🏆 Fastest Solution | 👍 Detailed Explanation
Intuition\n Describe your first thoughts on how to solve this problem. \n\n## Preprocessing\nWe have both positive numbers and negative numbers in the input. Th
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n## Preprocessing\nWe have both positive numbers and negative numbers in the input. They are actually very different. The **largest sum** is obviously the sum of **all** positive numbers, while the negative numbers will only enter the "picture" one by one.\nWe first choose all positive number to form our `offset` which is the largest sum, then we can convert all positive numbers to their negative part. For example, 3 becomes -3 and it is as if we have a -3 in the `nums`. For this -3, by "choose it" we actually mean "do not choose the original 3" and "do not choose this -3" means "choose the original 3". The final result of the new `nums` just need to add the `offset`.\n\n## Picking the first k elements and sort (decreasingly).\nOnce we have all numbers as negative, we get the nice *greedy property* of "sum of some numbers is worse than the individuals". Therefore we can concluded that we will never want to use an element in nums other than the first k elements (decreasing order).\n\n## Use a Priority Queue\nAgain we apply the *greedy property* and have the following conclustion: a combinations of some numbers `... + nums[i]` is always *worse* than `...` alone, assuming i is the largest index there. Hence, we can add the numbers into the queue one by one.\n\n  1. we put `{nums[0], 0}` in.\n  2. We pop the top element of the priority queue and if its index is not at the end, we push two new sums in `old_sum + nums[index + 1]` and `old_sum - nums[index] + nums[index + 1]`.\n  3. We record the poped element into an array.\n  4. We return the kth element of the array plus the `offset`.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe intuition above described the approach.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$\\Theta(N + k \\log k)$$\nThis is better than most other solutions as we used selection algorithm to pick the first `k` elements from `n` nums and only sort the first `k` elements, so we avoided the $N \\log N$ part.\n\n*Caveat*: The C++ standard does not require `std::nth_element()` to be implemented with worse case linear time algorithm and STL usually implements it with a version that has very good average linear time but worse case $\\Theta(N \\log N)$ time. It can be fixed by switching `std::nth_element()` with other libraries. Nevertheless it is practically good enough (and much faster than a full array sort).\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$\\Theta(k)$$ extra space.\n\nAs I finished the solution, I noticed that I can actually omit the array and only record the count and last element. It would save an array but the space complexity is still the same as the priority queue could use k space\n\n# Code\n```\nclass Solution {\npublic:\n  long long kSum(vector<int>& nums, int k) {\n    int64_t offset = 0;\n    for (int& num : nums) {\n      if (num > 0) {\n        offset += num;\n        num = -num;\n      }\n    }\n    if (nums.size() > k) {\n      std::nth_element(nums.begin(), nums.begin() + k - 1, nums.end(),\n          std::greater());\n      nums.resize(k);\n    }\n    sort(nums.begin(), nums.end(), std::greater());\n    vector<int64_t> sums = {0};\n    sums.reserve(k);\n    priority_queue<pair<int64_t, int>> q;\n    q.push({nums.front(), 0});\n    // Omitted q.empty() check since we are guaranteed with enough nums.\n    while (sums.size() < k) {\n      auto [sum, index] = q.top();\n      // cout << sums.size() << ": ";\n      sums.push_back(sum);\n      // cout << sum << endl;\n      q.pop();\n      if (index + 1 >= nums.size()) {\n        continue;\n      }\n      int64_t new_sum = sum + nums[index + 1];\n      q.push({new_sum, index + 1});\n      q.push({new_sum - nums[index], index + 1});\n    }\n\n    return sums[k - 1] + offset;\n  }\n};\n```
['C++']