🍸 Selecting the Largest Sum Subsequence of Length K – LeetCode 2099 (C++ | JavaScript | Python )

Hey, algorithm enthusiasts! 🚀

Today, we explore a clean and greedy approach to one of LeetCode's simpler but clever problems: "2099. Find Subsequence of Length K With the Largest Sum."

At first glance, it feels like a straightforward sorting challenge, but what makes this interesting is how we maintain the original order of the subsequence while still capturing the top k values. Let's break it down methodically.

---

🧠 Problem Summary

Input:

• An integer array nums
• An integer k

Goal:

• Find a subsequence of length k with the largest sum.
• The subsequence must preserve the relative ordering of the original array.

Definition:

• A subsequence is formed by deleting zero or more elements without changing the order of the remaining elements.

---

🧩 Intuition

To maximize the sum of the subsequence:

• We want the k largest elements from the array.
• But since relative order matters, we can't just sort and slice.

Key Insight:

• Track the indices of the k largest values.
• Reconstruct the result by scanning the original array and selecting only those values.

This is a classic case where combining a min-heap selection (or nth_element) with sorting by indices lets us optimize both for value and order.

---

⚙️ Approach

1. Find the Threshold: Use nth_element (or min-heap) to determine the smallest number in the top k values.
2. Count Frequency: Count how many values are strictly greater than the threshold and how many equal to it can still be selected.
3. Reconstruct Subsequence: Traverse the original array and greedily add eligible values.

---

🧮 C++ Code

class Solution {
 public:
  vector<int> maxSubsequence(vector<int>& nums, int k) {
    vector<int> ans;
    vector<int> arr(nums);
    nth_element(arr.begin(), arr.end() - k, arr.end());
    const int threshold = arr[arr.size() - k];
    const int larger =
        ranges::count_if(nums, [&](int num) { return num > threshold; });
    int equal = k - larger;

    for (const int num : nums)
      if (num > threshold) {
        ans.push_back(num);
      } else if (num == threshold && equal) {
        ans.push_back(num);
        --equal;
      }

    return ans;
  }
};

---

💻 JavaScript Code

var maxSubsequence = function(nums, k) {
    const arr = [...nums].sort((a, b) => b - a).slice(0, k);
    const freq = new Map();

    for (let num of arr)
        freq.set(num, (freq.get(num) || 0) + 1);

    const res = [];
    for (let num of nums) {
        if (freq.get(num)) {
            res.push(num);
            freq.set(num, freq.get(num) - 1);
        }
        if (res.length === k) break;
    }
    return res;
};

---

🐍 Python Code

def maxSubsequence(nums, k):
    import heapq
    arr = heapq.nlargest(k, nums)
    count = collections.Counter(arr)
    res = []

    for num in nums:
        if count[num]:
            res.append(num)
            count[num] -= 1
        if len(res) == k:
            break

    return res

---

📝 Key Notes

• Time Complexity: O(n) for selection + O(n) for reconstruction
• Space Complexity: O(n) for auxiliary arrays/counters
• Carefully manage duplicates at the threshold value.
• Preserve order during reconstruction by processing original input.

---

✅ Final Thoughts

This is a great example of blending greedy logic with practical selection techniques like nth_element or heap manipulation. Although it’s categorized as "Easy", managing the edge cases (like duplicate threshold elements) adds depth to the problem.

Keep learning and stay sharp! 💻✨

Happy coding! 🧠🔥

Comments

[Anna kowoski]

Well Explained !!!

[Om Shree]

Thanks Anna!!!