Find Subsequence of Length K With the Largest Sum Solution In C++/Python/Java/JS
Problem Description
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
Input: nums = [2,1,3,3], k = 2
Output: [3,3]
Explanation:
The subsequence has the largest sum of 3 + 3 = 6.
Input: nums = [-1,-2,3,4], k = 3
Output: [-1,3,4]
Explanation:
The subsequence has the largest sum of -1 + 3 + 4 = 6.
Constraints
- 1 <= nums.length <= 1000
- -10^5 <= nums[i] <= 10^5
- 1 <= k <= nums.length
Sort numbers by value while keeping track of their original indices. Use sorting and a min heap to efficiently select the top k elements while preserving their original order.
Brute Force Approach
Intuition
Our goal is to find a subsequence of length k with the largest sum while preserving the relative order of elements.
To achieve this, we first identify the k largest elements, as they contribute the most to the sum. However, simply picking the largest elements without considering their positions would break the order.
To handle this, we first sort the elements in descending order based on value and pick the top k. Since sorting disrupts the original order, we then re-sort these k elements based on their original indices to maintain the subsequence order.
This approach ensures that we maximize the sum while keeping the elements in their original sequence.
Approach
Step 1: Store Element Indices
- Create an array of pairs (value, index) where each pair stores:
- The element value.
- The original index of that element.
- This helps in tracking the original order after selecting the top k elements.
Step 2: Sort Elements by Value (Descending)
- Sort the array based on values in descending order so that the largest elements come first.
- This ensures that we can easily pick the k largest values.
Step 3: Select the Top K Elements - Pick the first k elements from the sorted array since they are the largest.
- Each element is stored along with its original index, so we do not lose track of the positions.
Step 4: Sort Selected Elements by Original Index
- Since a subsequence must maintain the original order, we sort the selected k elements by their original indices.
- This ensures that when we extract the values, they appear in the correct sequence.
Step 5: Extract and Return the Result
- Extract only the values from the sorted list and return them.
Dry Run
Input:
- nums = [2, 1, 3, 3], k = 2
Step 1: Store Element Indices
- We create an array of pairs (value, index):
- pairs=[(2,0),(1,1),(3,2),(3,3)]
Step 2: Sort Elements by Value (Descending)
- Sorting in descending order of values:
- sorted pairs=[(3,2),(3,3),(2,0),(1,1)]
Step 3: Select the Top K Elements
- We select the first k=2 elements:
- topK=[(3,2),(3,3)]
Step 4: Sort Selected Elements by Original Index
- Sorting by original index:
- sorted topK=[(3,2),(3,3)]
Step 5: Extract and Return the Result
- Extracting values: result = [3,3]
Final Output: [3,3]
Code for All Languages
C++
// Approach 1: Sorting with Indices
// Language: C++
class Solution {
public:
vector<int> maxSubsequence(vector<int>& nums, int k) {
int n = nums.size();
// Step 1: Create pairs of (value, index) for each element
vector<pair<int, int>> pairs;
for (int i = 0; i < n; i++) {
pairs.push_back({nums[i], i});
}
// Step 2: Sort pairs by value in descending order
sort(pairs.begin(), pairs.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
return a.first > b.first;
});
// Step 3: Select top K pairs (the K largest values)
vector<pair<int, int>> topK(pairs.begin(), pairs.begin() + k);
// Step 4: Sort these K pairs by their original indices to maintain the original order
sort(topK.begin(), topK.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
return a.second < b.second;
});
// Step 5: Extract and return the values in the original order
vector<int> result;
for (auto& p : topK) {
result.push_back(p.first);
}
return result;
}
};Java
// Approach : Sorting with Indices
// Language: Java
import java.util.*;
class Solution {
public int[] maxSubsequence(int[] nums, int k) {
int n = nums.length;
// Step 1: Create array of pairs (value, index)
int[][] pairs = new int[n][2];
for (int i = 0; i < n; i++) {
pairs[i][0] = nums[i]; // value
pairs[i][1] = i; // index
}
// Step 2: Sort pairs by value in descending order
Arrays.sort(pairs, (a, b) -> Integer.compare(b[0], a[0]));
// Step 3: Select top K pairs (the K largest values)
int[][] topK = new int[k][2];
for (int i = 0; i < k; i++) {
topK[i] = pairs[i];
}
// Step 4: Sort these K pairs by their original indices to maintain the original order
Arrays.sort(topK, (a, b) -> Integer.compare(a[1], b[1]));
// Step 5: Extract and return the values in the original order
int[] result = new int[k];
for (int i = 0; i < k; i++) {
result[i] = topK[i][0];
}
return result;
}
}Python
# Approach: Sorting with Indices
# Language: Python
class Solution(object):
def maxSubsequence(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
# Step 1: Create pairs of (value, index)
pairs = [(num, i) for i, num in enumerate(nums)]
# Step 2: Sort pairs by value in descending order
pairs.sort(key=lambda x: -x[0])
# Step 3: Select top K elements
topK = sorted(pairs[:k], key=lambda x: x[1])
# Step 4: Extract and return the values in original order
return [num for num, _ in topK]
Javascript
/**
* Approach: Sorting with Indices
* Language: JavaScript
*
* @param {number[]} nums - Input array of numbers.
* @param {number} k - Length of the subsequence to select.
* @return {number[]} - Subsequence of length k with the largest sum.
*/
var maxSubsequence = function(nums, k) {
// Step 1: Create pairs of (value, index)
let pairs = nums.map((num, index) => [num, index]);
// Step 2: Sort pairs by value in descending order
pairs.sort((a, b) => b[0] - a[0]);
// Step 3: Select top K elements
let topK = pairs.slice(0, k);
// Step 4: Sort selected elements by original index
topK.sort((a, b) => a[1] - b[1]);
// Step 5: Extract and return the values in original order
return topK.map(pair => pair[0]);
};
Time Complexity Analysis:O(nlogn)
Creating Pairs (O(n))
- We iterate through the nums array to create (value, index) pairs.
- Time Complexity: O(n)
Sorting by Value (O(n log n))
- We sort the pairs in descending order based on values.
- Time Complexity: O(nlogn)
Selecting Top k Elements (O(k))
- Extracting the first k elements from the sorted list.
- Time Complexity: O(k)
Sorting Selected Elements by Original Index (O(k log k))
- Sorting the top k elements based on their original indices.
- Time Complexity: O(klogk)
Extracting Final Values (O(k))
- Extracting values from the sorted topK list.
- Time Complexity: O(k)
Final Time Complexity: O(n log n) + O( klogk) O(n) ≈ O(n logn)
Since k ≤ n, the dominant term is O(nlogn), making it the final complexity.
Space Complexity Analysis: O(n + k)
Storing Pairs (O(n))
- We store (value, index) pairs in an array of size n, requiring O(n) space.
Selecting Top k Elements (O(k))
- We store the k largest elements in a separate array, requiring O(k) space.
Auxiliary Space (O(n))
- Sorting is done in place, but the storage for the sorted list still takes O(n).
Final Space Complexity: O(n)+O(k)=O(n+k)
The brute-force approach involved sorting all elements and generating combinations, leading to high time complexity. To optimize, we use a Min Heap (Priority Queue) strategy. Instead of sorting the entire array and selecting the top k elements separately, we maintain a min heap of size k, ensuring that only the k largest elements remain in the heap. This allows efficient element selection in O(n log k) time. After extracting these elements, sorting them by their original indices preserves the subsequence order. This significantly reduces computational overhead, making the solution much faster.
Optimal Approach
Intuition
The initial approach involved sorting the entire array and selecting the k largest elements, followed by sorting them again to maintain their original order. While correct, this approach had unnecessary computational overhead.
To optimize, we use a min heap (priority queue) to dynamically maintain the top k elements as we iterate through the array. Instead of sorting the entire array, we only keep track of the k largest elements seen so far. This ensures that we efficiently discard smaller elements, keeping only the most valuable ones.
By sorting the selected elements by their original indices, we preserve the subsequence order without needing an additional full sort. This reduces the time complexity to O(n log k) instead of O(n log n), making the approach significantly more efficient.
Approach
Step 1: Use a Min Heap to Maintain the Top k Elements
- We traverse the array while maintaining a min heap that stores the top k elements based on their values.
- This allows us to efficiently remove the smallest element whenever we exceed k, ensuring that we always retain the largest k values.
Step 2: Store Indices to Preserve Original Order
- Since we need to return the subsequence in its original order, we store both the value and its index in the heap.
- After extracting the top k elements, we sort them by their original indices to maintain the correct order.
Step 3: Construct the Result from the Sorted Indices
- Once we have the k largest elements in order, we extract their values to form the final subsequence.
Step 4: Return the Result
- The final vector contains the k largest elements in their original order, ensuring correctness with an optimized time complexity of O(n log k).
Dry Run
Input:
- nums = [2, 1, 3, 3], k = 2
Step 1: Process the Elements Using a Min Heap
- We traverse the array and maintain a min heap of size at most k, ensuring we retain the top k largest values while maintaining their indices.
Iteration 1: Process 2 (Index 0)
- Add (2, 0) to the heap → minHeap = [(2, 0)]
- Heap size < k, so we continue.
Iteration 2: Process 1 (Index 1)
- Add (1, 1) to the heap → minHeap = [(1, 1), (2, 0)]
- Heap size < k, so we continue.
Iteration 3: Process 3 (Index 2)
- Add (3, 2) to the heap → minHeap = [(1, 1), (2, 0), (3, 2)]
- Heap size exceeds k, remove the smallest element (1, 1).
- Heap after removal → minHeap = [(2, 0), (3, 2)].
Iteration 4: Process 3 (Index 3)
- Add (3, 3) to the heap → minHeap = [(2, 0), (3, 2), (3, 3)]
- Heap size exceeds k, remove the smallest element (2, 0).
- Heap after removal → minHeap = [(3, 2), (3, 3)].
Step 2: Extract Elements While Maintaining Original Order
- The heap contains the top k elements {(3,2), (3,3)} but not in their original order. We extract their indices from the original array and sort them to preserve their relative positions.
- Index Value Kept in Heap?
- 0 2 ❌ Removed
- 1 1 ❌ Removed
- 2 3 ✅ Kept
- 3 3 ✅ Kept
Step 3: Construct the Final Subsequence
- From the original array, selecting elements {3, 3} in the correct order gives:]
Final Output: [3,3]
Code for All Languages
C++
// Approach : Min Heap (Priority Queue)
// Language: C++
class Solution {
public:
vector<int> maxSubsequence(vector<int>& nums, int k) {
int n = nums.size();
// If k equals the array size, return the entire array
if (k == n) return nums;
// Step 1: Create a min heap of pairs (value, index)
// This will keep the k largest elements we've seen so far
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minHeap;
// Step 2: Process the array elements
for (int i = 0; i < n; i++) {
// Add current element to the heap
minHeap.push({nums[i], i});
// If heap size exceeds k, remove the smallest element
if (minHeap.size() > k) {
minHeap.pop();
}
}
// Step 3: Extract indices of the K largest elements
vector<pair<int, int>> selected;
while (!minHeap.empty()) {
selected.push_back({minHeap.top().second, minHeap.top().first});
minHeap.pop();
}
// Step 4: Sort indices to maintain original order
sort(selected.begin(), selected.end());
// Step 5: Construct result using these indices
vector<int> result;
for (auto& pair : selected) {
result.push_back(pair.second);
}
return result;
}
};
Java
// Approach : Min Heap (Priority Queue)
// Language: Java
import java.util.*;
class Solution {
public int[] maxSubsequence(int[] nums, int k) {
int n = nums.length;
// If k equals the array size, return the entire array
if (k == n) return nums;
// Step 1: Create a min heap of pairs (value, index)
// This will keep the k largest elements we've seen so far
PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
// Step 2: Process the array elements
for (int i = 0; i < n; i++) {
// Add current element to the heap
minHeap.offer(new int[]{nums[i], i});
// If heap size exceeds k, remove the smallest element
if (minHeap.size() > k) {
minHeap.poll();
}
}
// Step 3: Extract indices of the K largest elements
List<int[]> selected = new ArrayList<>();
while (!minHeap.isEmpty()) {
int[] pair = minHeap.poll();
selected.add(new int[]{pair[1], pair[0]}); // Store as (index, value)
}
// Step 4: Sort by original indices to maintain the order
Collections.sort(selected, (a, b) -> Integer.compare(a[0], b[0]));
// Step 5: Construct result using these indices
int[] result = new int[k];
for (int i = 0; i < k; i++) {
result[i] = selected.get(i)[1]; // Get the value from (index, value) pair
}
return result;
}
}Python
# Approach: Min Heap (Priority Queue)
# Language: Python
import heapq
class Solution(object):
def maxSubsequence(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
# Step 1: Use a min heap to store the k largest elements with their indices
minHeap = []
for i, num in enumerate(nums):
heapq.heappush(minHeap, (num, i)) # Push (value, index)
if len(minHeap) > k:
heapq.heappop(minHeap) # Remove the smallest element if size exceeds k
# Step 2: Extract indices of selected elements and sort them to maintain original order
selected = sorted(minHeap, key=lambda x: x[1])
# Step 3: Return the values in the original order
return [num for num, _ in selected]
Javascript
/**
* Approach: Min Heap (Priority Queue)
* Language: JavaScript
*
* @param {number[]} nums - Input array.
* @param {number} k - Number of elements to select.
* @return {number[]} - The subsequence of k elements maintaining relative order.
*/
var maxSubsequence = function(nums, k) {
// Step 1: Use a min heap (priority queue) to store k largest elements with their indices
let minHeap = [];
for (let i = 0; i < nums.length; i++) {
minHeap.push([nums[i], i]); // Push (value, index)
minHeap.sort((a, b) => a[0] - b[0]); // Sort by value in ascending order
if (minHeap.length > k) {
minHeap.shift(); // Remove the smallest element if size exceeds k
}
}
// Step 2: Extract indices of selected elements and sort them to maintain original order
minHeap.sort((a, b) => a[1] - b[1]); // Sort by index to preserve order
// Step 3: Return the values in the original order
return minHeap.map(pair => pair[0]);
};
Time Complexity Analysis: O(n log n + k log k)
Pair Creation and Sorting: O(n log n)
- We create n pairs (value, index) from the input array.
- Sorting these pairs by value in descending order takes O(n log n) time.
Min Heap Operations: O(k log k)
- We maintain a min heap to track the top k elements.
- Each insertion into the heap takes O(log k) time.
- Since we insert k elements, this step takes O(k log k) time.
Sorting Selected Elements by Index: O(k log k)
- After selecting the top k elements, we sort them by their original index to maintain order.
- Sorting k elements takes O(k log k) time.
Final Time Complexity: O(n log n + k log k)
- Since k ≤ n, we simplify to O(n log n ), which is efficient for large inputs.
Space Complexity Analysis: O(n)
Auxiliary Space Complexity: O(n)
- We store n pairs (value, index), requiring O(n) space.
- A min heap (priority queue) maintains at most k elements, requiring O(k) space.
- Other variables (topK, loop counters) require O(1) space.
Input Storage: O(n)
- The input array nums takes O(n) space.
- Sorting is done in place, so no extra space is needed.
Final Space Complexity:O(n) (input storage) + O(k) (heap) = O(n) (since k ≤ n).
Similar Problems
Now we have successfully tackled this problem, let’s try these similar problems.
Given a set of classes where each class has a certain number of passing students and total students, and extra students who are guaranteed to pass, the goal is to distribute these extra students in a way that maximizes the overall average pass ratio across all classes.
Given two integer arrays nums1 and nums2 of equal length n, and an integer k, select a subsequence of k indices from nums1.
The score of a chosen subsequence is defined as:
(sum of selected elements from nums1)×(minimum of selected elements from nums2)
Return the maximum possible score.