Find Subsequence of Length K With the Largest Sum
EasyPrompt
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.length
Approaches
3 approaches with complexity analysis and trade-offs.
The core idea is that the subsequence with the largest sum must consist of the k largest elements from the original array. A straightforward way to find these elements is to sort the array. However, sorting the array directly would lose the original relative order of the elements, which is a requirement for a subsequence. To overcome this, we can store each element along with its original index, sort based on the element's value, select the top k elements, and then restore their original order by sorting them again based on their original indices.
Algorithm
- Create a 2D array or a list of objects to store pairs of
(value, original_index)for each element innums. - Sort these pairs in descending order based on the
value. - Select the first
kpairs from the sorted list. These represent theklargest elements. - Sort these
kpairs in ascending order based on theiroriginal_indexto restore the subsequence order. - Create the final result array by extracting the
valuefrom each of thekindex-sorted pairs.
Walkthrough
This method ensures we identify the k largest values while being able to reconstruct their original relative ordering.
Here's the breakdown of the algorithm:
- Create Indexed Pairs: We first iterate through the input array
numsand create a new data structure, typically a 2D array or a list of custom objects. Each element in this structure will hold two pieces of information: the number itself (nums[i]) and its original position in the array (i). - Sort by Value: We then perform a sort on this new structure. The sorting criterion is the value of the number, in descending order. This brings the largest numbers to the front.
- Select Top K: After sorting, the first
kelements in our structure are theklargest values from the original array. We select thesekpairs. - Sort by Index: These
kpairs are now sorted by value, not by their original position. To restore the subsequence order, we perform a second sort on just thesekpairs, this time using their original index as the key, in ascending order. - Construct Result: Finally, we iterate through the
kindex-sorted pairs and extract just the values to build our final result array.
import java.util.Arrays; class Solution { public int[] maxSubsequence(int[] nums, int k) { int n = nums.length; // 1. Store pairs of (value, index) int[][] indexedNums = new int[n][2]; for (int i = 0; i < n; i++) { indexedNums[i][0] = nums[i]; indexedNums[i][1] = i; } // 2. Sort by value in descending order Arrays.sort(indexedNums, (a, b) -> b[0] - a[0]); // 3. Take the top k elements int[][] topK = new int[k][2]; for (int i = 0; i < k; i++) { topK[i] = indexedNums[i]; } // 4. Sort the top k elements by their original index Arrays.sort(topK, (a, b) -> a[1] - b[1]); // 5. Extract the values to form the result subsequence int[] result = new int[k]; for (int i = 0; i < k; i++) { result[i] = topK[i][0]; } return result; }}Complexity
Time
O(n log n) - The dominant step is sorting the n elements, which takes O(n log n). Creating the indexed array is O(n), and sorting the k elements takes O(k log k).
Space
O(n) - We need an auxiliary array of size n to store the (value, index) pairs.
Trade-offs
Pros
Relatively simple to understand and implement.
The O(n log n) performance is guaranteed and is efficient enough for the given constraints.
Cons
Not the most optimal solution as it sorts the entire array, which is more work than necessary.
Requires O(n) auxiliary space, which is more than some more optimized approaches.
This approach improves upon sorting by finding the k largest elements more efficiently. Instead of sorting the entire array, we can maintain a min-heap of size k. We iterate through the array, and for each element, we compare it with the smallest element in our heap (the root). If the current element is larger, we replace the root with the current element. After one pass, the heap contains the k largest elements. The challenge of preserving order is then solved by identifying which elements from the original array belong to this set of k largest values using a frequency map.
Algorithm
- Use a min-heap (PriorityQueue in Java) of size
kto find theklargest elements in a single pass. - Iterate through
nums. For each number, add it to the heap. If the heap's size grows larger thank, remove the smallest element (the root of the min-heap). - After the pass, the heap contains the
klargest elements. Create a frequency map of these elements. - Iterate through the original
numsarray again. If the current number exists in the frequency map with a count greater than zero, add it to the result and decrement its count in the map. - Return the constructed result array.
Walkthrough
This method avoids a full O(n log n) sort by using a data structure optimized for finding top elements.
Here's the breakdown of the algorithm:
- Find K Largest with a Min-Heap: We initialize a min-heap. We then iterate through the
numsarray. For eachnum, we add it to the heap. To ensure the heap only holds the largest elements seen so far, we check if its size has exceededk. If it has, wepoll()the smallest element, which is always at the root of a min-heap. This process takesO(n log k)time, as each of thenelements involves a heap operation that costsO(log k). - Create Frequency Map: Once we have the
klargest elements in our heap, we need a way to pick them out from the originalnumsarray while preserving order. A frequency map (like aHashMap) is perfect for this. We populate the map with the elements from the heap, counting how many times each value appears. - Build the Subsequence: We iterate through the original
numsarray a second time. For eachnum, we check our frequency map. If the map contains thenumand its associated count is positive, it means this is one of theklargest elements we're looking for. We add it to our result array and decrement its count in the map. This ensures we pick the correct number of duplicates and that they appear in their original relative order.
import java.util.HashMap;import java.util.Map;import java.util.PriorityQueue; class Solution { public int[] maxSubsequence(int[] nums, int k) { // 1. Use a min-heap to find the k largest elements. PriorityQueue<Integer> minHeap = new PriorityQueue<>(); for (int num : nums) { minHeap.offer(num); if (minHeap.size() > k) { minHeap.poll(); } } // 2. Create a frequency map of the k largest elements. Map<Integer, Integer> freqMap = new HashMap<>(); for (int num : minHeap) { freqMap.put(num, freqMap.getOrDefault(num, 0) + 1); } // 3. Build the result subsequence by iterating through the original array. int[] result = new int[k]; int index = 0; for (int num : nums) { if (freqMap.getOrDefault(num, 0) > 0) { result[index++] = num; freqMap.put(num, freqMap.get(num) - 1); } } return result; }}Complexity
Time
O(n log k) - Iterating through n elements with heap operations taking O(log k) each. The final scan is O(n).
Space
O(k) - The heap stores at most k+1 elements, and the frequency map stores at most k unique elements.
Trade-offs
Pros
More efficient than the O(n log n) sorting approach, especially when k is much smaller than n.
Uses less auxiliary space (O(k)) compared to the sorting approach (O(n)).
Cons
Slightly more complex to reason about than the sorting approach, especially regarding the handling of duplicate values.
This is the most optimal approach on average. The problem can be reframed as finding the (n-k)-th smallest element in the array. Any element larger than this value must be part of the result. Elements equal to this value might be needed to fill the subsequence up to length k. The Quickselect algorithm (a variant of Quicksort) can find the i-th smallest/largest element in an array in average linear time.
Algorithm
- The problem can be viewed as finding the
(n-k)-th smallest element. Let's call this thethreshold. - Use the Quickselect algorithm to find this
thresholdvalue inO(n)average time. - Count how many elements in the original array are strictly greater than the
threshold(count_greater). - Determine how many elements equal to the
thresholdare needed:count_equal_needed = k - count_greater. - Iterate through the original
numsarray. Add any element> thresholdto the result. Add any element== thresholdto the result as long ascount_equal_needed > 0, decrementing the count each time. - This builds the final subsequence of length
kin the correct order.
Walkthrough
This approach leverages a powerful selection algorithm to achieve linear time complexity on average. Instead of fully sorting, we only find the specific element that partitions the array into the numbers we want and the numbers we don't.
Here's the breakdown of the algorithm:
- Find the Threshold: The key insight is that if we sort the array, the
klargest elements would be at indicesn-kthroughn-1. The element at indexn-kis our cutoff point, orthreshold. We don't need to fully sort to find this; we can use Quickselect to find the(n-k)-th smallest element inO(n)average time. For simplicity, the code below usesArrays.sort(), which isO(n log n), to find this threshold, but a true Quickselect implementation would be faster. - Count Elements: Once we have the
threshold, we need to handle duplicates. An element might be equal to the threshold, but we may or may not need it. We first count how many elements in the original array are strictly greater than thethreshold. Let this becount_greater. - Determine Needed Duplicates: The number of slots left in our subsequence is
k - count_greater. This is exactly how many elements equal to thethresholdwe must include. Let this becount_equal_needed. - Construct Result: We make a final pass through the original
numsarray to build the result in the correct order. We add any element that is greater than thethreshold. We also add elements equal to thethresholduntil we have fulfilled ourcount_equal_neededquota.
import java.util.Arrays; class Solution { public int[] maxSubsequence(int[] nums, int k) { int n = nums.length; int[] sortedCopy = Arrays.copyOf(nums, n); // A true Quickselect would find this in O(n) average time. // For simplicity, we use sort which is O(n log n). Arrays.sort(sortedCopy); // 1. Find the threshold value. int threshold = sortedCopy[n - k]; // 2. Count how many elements are > threshold. int countGreater = 0; for (int num : nums) { if (num > threshold) { countGreater++; } } // 3. Determine how many elements equal to the threshold are needed. int countEqualNeeded = k - countGreater; // 4. Build the result by iterating through the original array. int[] result = new int[k]; int index = 0; for (int num : nums) { if (index == k) break; if (num > threshold) { result[index++] = num; } else if (num == threshold && countEqualNeeded > 0) { result[index++] = num; countEqualNeeded--; } } return result; }}Complexity
Time
O(n) on average, O(n^2) in the worst case. Finding the k-th element via Quickselect is O(n) on average. The subsequent passes are also O(n).
Space
O(n) or O(log n) - A true Quickselect can be done in-place with O(log n) recursion stack space. The simplified code shown uses O(n) for a copy of the array.
Trade-offs
Pros
Asymptotically the fastest approach with an average time complexity of O(n).
Highly efficient for large inputs where the difference between O(n) and O(n log k) is significant.
Cons
The worst-case time complexity is O(n^2), which can occur with consistently poor pivot choices in the Quickselect algorithm.
A proper implementation of Quickselect is more complex than using built-in sorting or heap data structures.
Solutions
Solution
class Solution {public int[] maxSubsequence(int[] nums, int k) { int[] ans = new int[k]; List<Integer> idx = new ArrayList<>(); int n = nums.length; for (int i = 0; i < n; ++i) { idx.add(i); } idx.sort(Comparator.comparingInt(i->- nums[i])); int[] t = new int[k]; for (int i = 0; i < k; ++i) { t[i] = idx.get(i); } Arrays.sort(t); for (int i = 0; i < k; ++i) { ans[i] = nums[t[i]]; } return ans; }}class Solution {public: vector<int> maxSubsequence(vector<int> &nums, int k) { int n = nums.size(); vector<pair<int, int>> vals; for (int i = 0; i < n; ++i) vals.push_back({i, nums[i]}); sort(vals.begin(), vals.end(), [&](auto x1, auto x2) { return x1.second > x2.second; }); sort(vals.begin(), vals.begin() + k); vector<int> ans; for (int i = 0; i < k; ++i) ans.push_back(vals[i].second); return ans; }};class Solution: def maxSubsequence(self, nums: List[int], k: int) -> List[int]: idx = list(range(len(nums))) idx . sort(key=lambda i: nums[i]) return [nums[i] for i in sorted(idx[- k:])]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.