Scale Engineer

Find Subsequence of Length K With the Largest Sum

Easy
#1911Time: 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.2 companies
Algorithms
Sorting
Data structures
ArrayHash TableHeap (Priority Queue)
Companies
AccentureOracle

Prompt

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

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 in nums.
  • Sort these pairs in descending order based on the value.
  • Select the first k pairs from the sorted list. These represent the k largest elements.
  • Sort these k pairs in ascending order based on their original_index to restore the subsequence order.
  • Create the final result array by extracting the value from each of the k index-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:

  1. Create Indexed Pairs: We first iterate through the input array nums and 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).
  2. 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.
  3. Select Top K: After sorting, the first k elements in our structure are the k largest values from the original array. We select these k pairs.
  4. Sort by Index: These k pairs are now sorted by value, not by their original position. To restore the subsequence order, we perform a second sort on just these k pairs, this time using their original index as the key, in ascending order.
  5. Construct Result: Finally, we iterate through the k index-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.

Solutions

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;  }}

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.

← Previous

Previous problem

Next →

Next problem