2099. Find Subsequence of Length K With the Largest Sum

EasyArrayHash TableSortingHeap (Priority Queue)

Problem Description

In this problem, we are given an array of integers named nums and another integer k. Our goal is to find a subsequence of the array nums that consists of k elements and has the largest possible sum. A subsequence is defined as a sequence that can be obtained from the original array by removing some or no elements, without changing the order of the remaining elements. The problem statement requires us to return any subsequence that satisfies the condition of having k elements and the largest sum. If there are multiple subsequences with the same largest sum, we can return any one of them.

Intuition

To approach this solution, we need to focus on finding the elements that would contribute to the largest sum. Naturally, larger numbers will contribute more to the sum than smaller numbers. Therefore, the subsequence with the largest sum within a given size k will always include the k largest elements from the original nums array.

However, since we are interested in a subsequence, it's important to maintain the original order of elements. The provided solution achieves this by first finding the indices of the k largest elements, and then reconstructing the subsequence by accessing the elements using these indices in their sorted order.

The solution starts by creating a list of indices idx for all elements in nums.
It sorts this list of indices idx based on the values in nums that they correspond to, using a lambda function as the key to the sort method.
By sorting idx, the last k indices now represent the largest k numbers in nums.
The subsequence is then created by selecting the elements of nums using the sorted list of the last k indices.
Since we need to return the subsequence in its original order, we sort the list of the last k indices, ensuring that the corresponding k elements will be in the same order as they appeared in nums.

By following this method, we can efficiently retrieve any subsequence of length k that yields the largest sum while maintaining its original order from nums.

Learn more about Sorting and Heap (Priority Queue) patterns.

Solution Approach

In the provided reference solution, several key programming concepts and Python-specific tools are employed to extract the k largest sum subsequence:

List Comprehension: Python's list comprehension is used to concisely generate lists without writing out complex for-loops. In this solution, list comprehensions are used twice, once to generate the sorted indices and then to generate the actual subsequence.
Sorting with Custom Key Function: list.sort() method is used with a custom key function. The key function is provided by a lambda expression lambda i: nums[i] which sorts the list of indices idx based on the value of elements in nums at each index.
Slicing: Python's slicing operation [-k:] is used to obtain the last k elements from the sorted list of indices, which represents the indices of the k largest numbers.

The steps to implement this approach are as follows:

Start by creating a list of indices idx with range(len(nums)) which basically gives us a list [0, 1, 2, ..., len(nums) - 1]. Each index here is a direct reference to the corresponding element in nums.
Next, sort the list idx using the sort method with a key that references the original list's values nums[i]. After sorting, for an array nums = [1, 3, 5, 7, 9], and say k = 3, the idx array will look like [4, 3, 2, 1, 0] because we are sorting by the values of nums in descending order.
Slice the last k elements from the sorted idx to get the indices of the k largest elements. For our example, we will get [4, 3, 2].
Before creating the final subsequence, we need to ensure that its order is the same as the original array's order. We achieve this by sorting the slice of indices.
Finally, the solution applies the sorted indices to nums to produce the subsequence with the largest sum. We use a list comprehension to achieve this: [nums[i] for i in sorted(idx[-k:])].

This algorithm effectively combines Python's powerful list manipulation features to provide a simple yet efficient solution. The complexity of the solution is dominated by the sorting step, which is typically O(n log n) where n is the number of elements in nums.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's take a small sample array nums = [7, 1, 5, 3, 6, 4] and assume we want a subsequence of length k = 3 with the largest sum.

Initial Steps

First, create an array of indices, idx, which will initially be [0, 1, 2, 3, 4, 5].

Sorting by Reference to nums Values

Next, we sort the idx array while referencing the elements it points to in nums. The sorting will be done in descending order based on the values in nums, which means the highest numbers come first:
- After sorting, idx becomes [0, 4, 2, 5, 3, 1] since the corresponding nums values are [7, 6, 5, 4, 3, 1].

Slicing to Get Largest Elements

Then we take the last k elements of the sorted idx. In this case k = 3, so we slice the last three indices, getting [2, 5, 3] which corresponds to nums values [5, 4, 3].

Sorting Indices to Maintain Original Order

Before creating the final subsequence, sort the slice [2, 5, 3] to maintain the original order of elements from nums. When we sort this slice, we get [2, 3, 5].

Creating the Final Subsequence

Using these sorted indices, we construct our subsequence by taking the values from nums at these positions, hence [nums[i] for i in sorted(idx[-k:])] becomes [nums[2], nums[3], nums[5]] which evaluates to [5, 3, 4].

Result

The subsequence [5, 3, 4] has a sum of 12, which is the largest sum possible for any 3 element subsequence in the original nums. Thus, the final answer for this example is [5, 3, 4].

In summary, by identifying and extracting the indices of the k largest numbers, sorting those indices to maintain the initial array's order, and then building a subsequence from these indices, we maximally leverage Python's list manipulation abilities to efficiently solve the problem.

Solution Implementation

1class Solution:
2    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:
3        # Create a list of indices that correspond to the elements in 'nums'.
4        indices = list(range(len(nums)))
5      
6        # Sort the list of indices based on the values in 'nums' they point to.
7        indices.sort(key=lambda i: nums[i])
8      
9        # Select the last 'k' elements from the sorted indices since they point to 
10        # the elements with the 'k' largest values in 'nums'.
11        largest_indices = indices[-k:]
12      
13        # Sort the selected indices to maintain the original order of 'nums'.
14        sorted_largest_indices = sorted(largest_indices)
15      
16        # Return the subsequence of 'nums' pointed by the sorted largest indices,
17        # which constitutes the k-largest elements in their original order.
18        max_subsequence = [nums[i] for i in sorted_largest_indices]
19      
20        return max_subsequence
21

1class Solution {
2    public int[] maxSubsequence(int[] nums, int k) {
3        // Initialize an array 'ans' to store the result subsequence of length k
4        int[] ans = new int[k];
5      
6        // Create a list 'indices' to keep track of the original indices of the array elements
7        List<Integer> indices = new ArrayList<>();
8      
9        // Loop to fill 'indices' with the array indices
10        for (int i = 0; i < nums.length; ++i) {
11            indices.add(i);
12        }
13      
14        // Sort 'indices' based on the values in 'nums' from highest to lowest
15        indices.sort((i1, i2) -> Integer.compare(nums[i2], nums[i1]));
16      
17        // Initialize a temporary array 'topIndices' to store the first k sorted indices
18        int[] topIndices = new int[k];
19        for (int i = 0; i < k; ++i) {
20            topIndices[i] = indices.get(i);
21        }
22      
23        // Sort 'topIndices' to maintain the original order of selected k elements
24        Arrays.sort(topIndices);
25      
26        // Fill the 'ans' array with the elements corresponding to the sorted indices
27        for (int i = 0; i < k; ++i) {
28            ans[i] = nums[topIndices[i]];
29        }
30      
31        // Return the result array containing the max subsequence of length k
32        return ans;
33    }
34}
35

1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6    // Method to find the subsequence of 'k' numbers with the largest sum
7    vector<int> maxSubsequence(vector<int>& nums, int k) {
8        // Size of the input array
9        int numSize = nums.size();
10
11        // Pair of index and value from the input array
12        vector<pair<int, int>> indexedNums;
13
14        // Populate the indexedNums with pairs of indices and their respective values
15        for (int i = 0; i < numSize; ++i) {
16            indexedNums.push_back({i, nums[i]});
17        }
18
19        // Sort the indexedNums by their values in descending order
20        sort(indexedNums.begin(), indexedNums.end(), [](const auto& x1, const auto& x2) {
21            return x1.second > x2.second;
22        });
23
24        // Sort only the first 'k' elements of indexedNums by their original indices to maintain the original order
25        sort(indexedNums.begin(), indexedNums.begin() + k,
26             [](const auto& x1, const auto& x2) {
27                 return x1.first < x2.first;
28             });
29
30        // Prepare a vector to store the answer subsequence
31        vector<int> ans;
32        ans.reserve(k); // Reserve space for 'k' elements to avoid reallocations
33
34        // Populate the answer vector with the 'k' largest elements in their original order
35        for (int i = 0; i < k; ++i) {
36            ans.push_back(indexedNums[i].second);
37        }
38
39        // Return the final answer subsequence
40        return ans;
41    }
42};
43

1function maxSubsequence(nums: number[], k: number): number[] {
2    // Size of the input array
3    let numSize: number = nums.length;
4
5    // Pair of index and value from the input array
6    let indexedNums: { index: number, value: number }[] = [];
7
8    // Populate the indexedNums with objects containing indices and their respective values
9    for (let i = 0; i < numSize; ++i) {
10        indexedNums.push({ index: i, value: nums[i] });
11    }
12
13    // Sort the indexedNums by their values in descending order
14    indexedNums.sort((a, b) => b.value - a.value);
15
16    // Sort only the first 'k' elements of indexedNums by their original indices to maintain the original order
17    let firstKElements: { index: number, value: number }[] = indexedNums.slice(0, k);
18    firstKElements.sort((a, b) => a.index - b.index);
19
20    // Prepare an array to store the answer subsequence
21    let answer: number[] = firstKElements.map(element => element.value);
22
23    // Return the final answer subsequence
24    return answer;
25}
26

Time and Space Complexity

The time complexity of the code is as follows:

Creating the idx list with list comprehension has a time complexity of O(n) where n is the number of elements in nums.
Sorting the idx list using the key, which is based on the values in nums, with the sort() function is O(n log n).
Slicing the last k elements from the sorted idx list is O(k) because it requires iterating over the k elements to create a new list.
Sorting the sliced list of k indices is O(k log k).
The list comprehension in the return statement to create the final list of numbers from their indices takes O(k).

The overall time complexity is therefore dominated by the O(n log n) step, which is the sorting of the idx list.

The space complexity of the code is:

The additional list idx that stores the indices takes O(n) space.
No additional space other than variables for sorting and slicing are used, which does not depend on the size of the input and hence is O(1).
The output list that is returned has k elements, so it takes O(k) space.

Therefore, the total space complexity is O(n + k), since you need to store the indices and the final output list.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: