Find Subsequence of Length K With the Largest Sum solution and explanation
TCS
Google
9 more videos on this problem
Find Subsequence of Length K With the Largest Sum | 2 Approaches | Leetcode 2099 | codestorywithMIKcodestorywithMIK · 40:42 · 7K views
Find Subsequence of Length K With the Largest Sum | Leetcode 2099 | Live coding session🔥🔥🔥Contest 67Coding Decoded · 8:49 · 6K views
2099 Find Subsequence of Length K With the Largest Sum (Leetcode Easy)Programming Live with Larry · 10:31 · 1K views
2099. Find Subsequence of Length K With the Largest Sum | Leetcode Daily - PythonLeetcode Daily · 4:15 · 1K views
2099. Find Subsequence of Length K With the Largest Sum | leetcode - 2099 | Java SolutioncodingX krishna · 13:55 · 922 views
Find Subsequence of Length K With the Largest Sum | LeetCode 2099 | Custom Sorting | Amazon OracleCode Harmony · 11:45 · 791 views
LeetCode 2099 - Find Subsequence of Length K With the Largest Sum || PQ-3 ||The Code Transaction · 8:29 · 675 views
Find Subsequence of Length K With the Largest Sum - Arrays & Hashing - LeetCode 2099Robin · 12:24 · 666 views
Daily Leetcode #1915: Jun 28, 2025 - 2099. Find Subsequence of Length K With the Largest SumProgramming Live with Larry · 6:55 · 575 views
Leetcode 2099 | Find Subsequence Of Length K With The Largest Sum | Leetcode POTDCoding Grower · 19:28 · 379 views
The problem
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
Approach overview
Problem 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 1: Sorting and Selecting Top K Elements
Approach: Sort the array of numbers based on their values while remembering their original indices. Then, select the top k elements with the largest values and use their indices to construct the subsequence from the original array.
This approach involves two main steps: sorting the array elements along with their original indices and selecting the largest k elements from this sorted structure. Once the top k elements are found, maintain their original order by using the stored indices.
def maxSubsequence(nums, k):
indexed_nums = [(num, i) for i, num in enumerate(nums)]
# Sort by number descending
indexed_nums.sort(reverse=True, key=lambda x: x[0])
selected_indices = [index for _, index in indexed_nums[:k]]
# Sort indices to maintain order
selected_indices.sort()
return [nums[i] for i in selected_indices]
# Example usage:
nums = [2, 1, 3, 3]
k = 2
result = maxSubsequence(nums, k)
print(result) # Output: [3, 3]import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class MaxSubsequence {
public static int[] maxSubsequence(int[] nums, int k) {
int[][] numWithIndex = new int[nums.length][2];
for (int i = 0; i < nums.length; i++) {
numWithIndex[i][0] = nums[i];
numWithIndex[i][1] = i;
}
Arrays.sort(numWithIndex, (a, b) -> b[0] - a[0]);
List<Integer> indices = new ArrayList<>();
for (int i = 0; i < k; i++) {
indices.add(numWithIndex[i][1]);
}
indices.sort(Integer::compareTo);
int[] result = new int[k];
for (int i = 0; i < k; i++) {
result[i] = nums[indices.get(i)];
}
return result;
}
public static void main(String[] args) {
int[] nums = {2, 1, 3, 3};
int k = 2;
int[] result = maxSubsequence(nums, k);
for (int num : result) {
System.out.print(num + " ");
}
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> maxSubsequence(vector<int>& nums, int k) {
vector<pair<int, int>> indexedNums;
for (int i = 0; i < nums.size(); ++i) {
indexedNums.emplace_back(nums[i], i);
}
sort(indexedNums.rbegin(), indexedNums.rend());
vector<int> selectedIndices;
for (int i = 0; i < k; ++i) {
selectedIndices.push_back(indexedNums[i].second);
}
sort(selectedIndices.begin(), selectedIndices.end());
vector<int> result;
for (int index : selectedIndices) {
result.push_back(nums[index]);
}
return result;
}
int main() {
vector<int> nums = {2, 1, 3, 3};
int k = 2;
vector<int> result = maxSubsequence(nums, k);
for (int num : result) {
cout << num << " ";
}
return 0;
}function maxSubsequence(nums, k) {
let indexedNums = nums.map((num, index) => [num, index]);
indexedNums.sort((a, b) => b[0] - a[0]);
let selectedIndices = indexedNums.slice(0, k).map(item => item[1]);
selectedIndices.sort((a, b) => a - b);
return selectedIndices.map(index => nums[index]);
}
// Example usage:
let nums = [2, 1, 3, 3];
let k = 2;
let result = maxSubsequence(nums, k);
console.log(result); // Output: [3, 3]#include <stdio.h>
#include <stdlib.h>
typedef struct {
int value;
int index;
} Element;
// Compare function for qsort
int compare(const void* a, const void* b) {
return ((Element*)b)->value - ((Element*)a)->value;
}
int* maxSubsequence(int* nums, int numsSize, int k, int* returnSize) {
// Create an array of Element structs
Element* elements = (Element*)malloc(numsSize * sizeof(Element));
for (int i = 0; i < numsSize; ++i) {
elements[i].value = nums[i];
elements[i].index = i;
}
// Sort elements in descending order of values
qsort(elements, numsSize, sizeof(Element), compare);
// Select k largest elements
int* selectedIndices = malloc(k * sizeof(int));
for (int i = 0; i < k; ++i) {
selectedIndices[i] = elements[i].index;
}
// Sort indices to maintain order in subsequence
qsort(selectedIndices, k, sizeof(int), compare);
// Build the result array based on selected indices
int* result = malloc(k * sizeof(int));
for (int i = 0; i < k; ++i) {
result[i] = nums[selectedIndices[i]];
}
free(elements);
free(selectedIndices);
*returnSize = k;
return result;
}
int main() {
int nums[] = {2, 1, 3, 3};
int k = 2;
int returnSize;
int* result = maxSubsequence(nums, 4, k, &returnSize);
for (int i = 0; i < returnSize; ++i) {
printf("%d ", result[i]);
}
free(result);
return 0;
}using System;
using System.Collections.Generic;
using System.Linq;
public class Program
{
public static int[] MaxSubsequence(int[] nums, int k)
{
var numsWithIndex = nums.Select((num, index) => new { num, index }).ToList();
numsWithIndex.Sort((a, b) => b.num.CompareTo(a.num));
List<int> indices = new List<int>();
for (int i = 0; i < k; i++)
{
indices.Add(numsWithIndex[i].index);
}
indices.Sort();
int[] result = new int[k];
for (int i = 0; i < k; i++)
{
result[i] = nums[indices[i]];
}
return result;
}
public static void Main()
{
int[] nums = { 2, 1, 3, 3 };
int k = 2;
int[] result = MaxSubsequence(nums, k);
Console.WriteLine(string.Join(" ", result));
}
}In this Python solution, the enumerate function is used to pair each number with its index. The list is sorted based on values in descending order, and the top k indices are selected and sorted again to form the desired subsequence from the original array.
Time Complexity: O(n log n), mainly due to the sorting step.
Space Complexity: O(n), for storing the element-index pairs.
Approach 2: Using Priority Queue (Min-Heap)
Approach: Utilize a Min-Heap (or Priority Queue) to keep track of the k largest elements in the array. This method involves iterating through the array and inserting each element into the heap, ensuring that the heap size does not exceed k. If the heap exceeds k elements, the smallest element is removed. This approach keeps only the top k elements.
Finally, extract the elements from the heap and reconstruct the subsequence in the order they appear in the original array using their indices.
import heapq
def maxSubsequence(nums, k):
min_heap = []
for i, num in enumerate(nums):
if len(min_heap) < k:
heapq.heappush(min_heap, (num, i))
else:
if num > min_heap[0][0]:
heapq.heapreplace(min_heap, (num, i))
indices = sorted([item[1] for item in min_heap])
return [nums[i] for i in indices]
# Example usage:
nums = [2, 1, 3, 3]
k = 2
result = maxSubsequence(nums, k)
print(result) # Output: [3, 3]import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Arrays;
public class MaxSubsequence {
public static int[] maxSubsequence(int[] nums, int k) {
PriorityQueue<int[]> minHeap = new PriorityQueue<>(k, (a, b) -> a[0] - b[0]);
for (int i = 0; i < nums.length; i++) {
if (minHeap.size() < k) {
minHeap.offer(new int[]{nums[i], i});
} else if (nums[i] > minHeap.peek()[0]) {
minHeap.poll();
minHeap.offer(new int[]{nums[i], i});
}
}
int[] indices = new int[k];
int[] result = new int[k];
int idx = 0;
while (!minHeap.isEmpty()) {
indices[idx++] = minHeap.poll()[1];
}
Arrays.sort(indices);
for (int i = 0; i < k; i++) {
result[i] = nums[indices[i]];
}
return result;
}
public static void main(String[] args) {
int[] nums = {2, 1, 3, 3};
int k = 2;
int[] result = maxSubsequence(nums, k);
for (int num : result) {
System.out.print(num + " ");
}
}
}Python's heapq module is used to manage a Min-Heap. The heap stores tuples of numbers and their indices. As we iterate through the array, numbers are added to the heap, and if its size exceeds k, the smallest element is popped. At the end, the indices are sorted and used to extract the required elements in order.
Time Complexity: O(n log k), because each insertion and removal from the heap has a log k time complexity.
Space Complexity: O(k), for maintaining the heap of size k.
Approach 3: Sorting
First, we create an index array idx, where each element is an index of the array nums. Then, we sort the index array idx based on the values in nums, with the sorting rule being nums[i] < nums[j], where i and j are two indices in the index array idx.
After sorting, we take the last k elements of the index array idx. These k elements correspond to the largest k elements in the array nums. Then, we sort these k indices to get the order of the largest k elements in the array nums.
The time complexity is O(n log n), and the space complexity is O(log n). Here, n is the length of the array.
function maxSubsequence(nums: number[], k: number): number[] {
const n = nums.length;
const idx: number[] = Array.from({ length: n }, (_, i) => i);
idx.sort((i, j) => nums[i] - nums[j]);
return idx
.slice(n - k)
.sort((i, j) => i - j)
.map(i => nums[i]);
}func maxSubsequence(nums []int, k int) []int {
idx := slices.Clone(make([]int, len(nums)))
for i := range idx {
idx[i] = i
}
slices.SortFunc(idx, func(i, j int) int { return nums[i] - nums[j] })
slices.Sort(idx[len(idx)-k:])
ans := make([]int, k)
for i := range ans {
ans[i] = nums[idx[len(idx)-k+i]]
}
return ans
}impl Solution {
pub fn max_subsequence(nums: Vec<i32>, k: i32) -> Vec<i32> {
let n = nums.len();
let k = k as usize;
let mut idx: Vec<usize> = (0..n).collect();
idx.sort_by_key(|&i| nums[i]);
idx[n - k..].sort();
let mut ans = Vec::with_capacity(k);
for i in n - k..n {
ans.push(nums[idx[i]]);
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sorting and Selecting Top K Elements | Time Complexity: O(n log n), mainly due to the sorting step. Space Complexity: O(n), for storing the element-index pairs. |
| Using Priority Queue (Min-Heap) | Time Complexity: O(n log k), because each insertion and removal from the heap has a log k time complexity. Space Complexity: O(k), for maintaining the heap of size k. |
| Sorting | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Find Subsequence of Length K With the Largest Sum easy or hard?
Find Subsequence of Length K With the Largest Sum is classified as an Easy problem on LeetCode. The main challenge is recognizing that you must select the k largest elements while preserving their original order. Once that insight is clear, the solution using sorting or a heap becomes straightforward.
Find Subsequence of Length K With the Largest Sum Python/Java solution
In Python or Java, one solution sorts pairs of (value, index), selects the top k values, and then sorts those k elements by index before returning the result. Another implementation uses a PriorityQueue or heapq to keep the k largest elements while iterating through the array. Both approaches ensure the final output preserves the original order.
How to solve Find Subsequence of Length K With the Largest Sum in O(n)?
A strict O(n) solution is generally not used for this problem because selecting the top k elements typically requires ordering operations. The closest practical optimization is the min-heap approach, which runs in O(n log k). It efficiently tracks the k largest values while scanning the array once.
What is the best approach for Find Subsequence of Length K With the Largest Sum?
The most efficient approach uses a min-heap (priority queue) of size k. Iterate through the array and push elements with their indices into the heap, removing the smallest when the heap exceeds k. This keeps the k largest elements while scanning the array once. The time complexity is O(n log k) with O(k) space.
Is Find Subsequence of Length K With the Largest Sum asked at Google/Amazon/Meta?
Problems involving selecting top-k elements and preserving order frequently appear in interviews at companies like Amazon, Google, and Meta. The question tests understanding of arrays, sorting strategies, and heap data structures. Variations of top-k problems are especially common in system design and algorithm rounds.
What data structure is used in Find Subsequence of Length K With the Largest Sum?
The main data structures are arrays and a priority queue (min-heap). The heap helps maintain the k largest elements efficiently while scanning the array. Sorting with index tracking is another common approach to restore the correct subsequence order.
What is the time complexity of Find Subsequence of Length K With the Largest Sum?
The common sorting-based solution runs in O(n log n) time because the array elements are sorted by value. The optimized approach using a min-heap runs in O(n log k) time since each insertion or removal from the heap costs log k. Space complexity is O(n) for sorting or O(k) for the heap solution.