Skip to main content
Talentd

Find Subsequence of Length K With the Largest Sum - Solution & Explanation

EasyArrayHash TableSortingHeap (Priority Queue)17 min readAsked at: Amazon, Meta, Accenture +3
Practice this problem

Problem Statement

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] <= 105
  • 1 <= 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.

This program sorts the array based on their values while keeping track of the original indices using a struct. The qsort function is utilized for sorting. After sorting, the top k elements are selected and arranged in the order they originally appeared in the input array.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n), due to sorting the elements.

Space Complexity: O(n), required for storing elements and indices.

Try this approach in the editor →

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.

This solution utilizes a Min-Heap in Java's PriorityQueue. Each entry in the queue is a pair consisting of the number and its index. As we iterate through the array, we keep adding pairs to the heap and ensure its size remains k by removing the smallest element when necessary. The final list of indices is sorted and used to form the resultant subsequence.

Code

JavaPython

Java

Python

Complexity

Time Complexity: O(n log k), because each insertion and deletion in the heap takes log k time.

Space Complexity: O(k), for storing the k largest elements.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sorting and Selecting Top K Elements

Time Complexity: O(n log n), due to sorting the elements.

Space Complexity: O(n), required for storing elements and indices.

Using Priority Queue (Min-Heap)

Time Complexity: O(n log k), because each insertion and deletion in the heap takes log k time.

Space Complexity: O(k), for storing the k largest elements.

Sorting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sorting and Selecting Top K ElementsO(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

Video Solution

Find Subsequence of Length K With the Largest Sum | 2 Approaches | Leetcode 2099 | codestorywithMIK • codestorywithMIK • 7,892 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Find Subsequence of Length K With the Largest Sum with our built-in code editor and test cases.

Practice on FleetCode
Previous

Kth Largest Element in an Array

Next

Maximize Sum Of Array After K Negations