Watch 10 video solutions for Find Subsequence of Length K With the Largest Sum, a easy level problem involving Array, Hash Table, Sorting. This walkthrough by codestorywithMIK has 7,674 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an integer array nums and an integer k. You want to find a subsequence of nums of length k that has the largest sum.
Return any such subsequence as an integer array of length k.
A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.
Example 1:
Input: nums = [2,1,3,3], k = 2 Output: [3,3] Explanation: The subsequence has the largest sum of 3 + 3 = 6.
Example 2:
Input: nums = [-1,-2,3,4], k = 3 Output: [-1,3,4] Explanation: The subsequence has the largest sum of -1 + 3 + 4 = 6.
Example 3:
Input: nums = [3,4,3,3], k = 2 Output: [3,4] Explanation: The subsequence has the largest sum of 3 + 4 = 7. Another possible subsequence is [4, 3].
Constraints:
1 <= nums.length <= 1000-105 <= nums[i] <= 1051 <= k <= nums.lengthProblem Overview: Given an integer array nums and an integer k, return a subsequence of length k with the largest possible sum. The subsequence must preserve the original order of elements in the array.
The key detail: you want the k largest values, but you must output them in the same relative order they appeared in the original array. That means you cannot simply sort and return the top elements; you must track their indices and restore the order.
Approach 1: Sorting and Selecting Top K Elements (O(n log n) time, O(n) space)
Pair every element with its index, then sort these pairs by value in descending order. After sorting, take the first k elements because they contribute the largest possible sum. These elements are not necessarily in the correct subsequence order, so sort the selected k pairs again by their original indices. Finally, extract the values in that order to produce the valid subsequence.
This approach is straightforward and easy to implement using standard sorting. The extra index sorting step ensures the subsequence constraint is preserved. For most interview scenarios, this method is perfectly acceptable and easy to reason about.
Approach 2: Using Priority Queue (Min-Heap) (O(n log k) time, O(k) space)
Maintain a min-heap that stores at most k elements. As you iterate through the array, push each element along with its index into the heap. If the heap size exceeds k, remove the smallest value. This guarantees the heap always contains the k largest elements seen so far.
Once the scan finishes, the heap contains exactly the elements forming the maximum-sum subsequence. Since heap order does not match the original array order, extract the elements and sort them by index before building the final result. This method leverages a priority queue to avoid sorting the entire array and reduces complexity when k is much smaller than n.
Recommended for interviews: The sorting solution clearly demonstrates the insight that the answer consists of the k largest values while preserving indices. The min-heap approach is more scalable with O(n log k) time and shows stronger understanding of priority queues and optimization techniques.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting and Selecting Top K Elements | O(n log n) | O(n) | Simple implementation when array size is moderate and readability matters |
| Priority Queue (Min-Heap) | O(n log k) | O(k) | Best when k is much smaller than n and you want a more optimal scalable solution |