Find Subsequence of Length K With Largest Sum — Top-K with Order Preservation

Problem Statement#

You are given an integer array nums and an integer k. Return a subsequence of nums of length k that has the largest possible sum. A subsequence preserves the relative order of elements from the original array.

If multiple subsequences tie for the largest sum, any of them is acceptable.

Constraints:

• 1 <= nums.length <= 1000
• -100000 <= nums[i] <= 100000
• 1 <= k <= nums.length

Input:  nums = [2,1,3,3], k = 2
Output: [3,3]
 
Input:  nums = [-1,-2,3,4], k = 3
Output: [-1,3,4]
 
Input:  nums = [3,4,3,3], k = 2
Output: [3,4]

Why This Problem Matters#

LeetCode 2099 (Find Subsequence of Length K With the Largest Sum) is a screening favourite at Amazon and Google because it splits a single innocent-looking question into two separate jobs: which elements should we pick, and in what order should we return them. Many candidates in their first heap interview conflate the two. A clean answer requires a heap (or quickselect) for selection and a stable secondary structure for order restoration. That is exactly the priority-queue interview muscle FAANG screens are testing.

The pattern shows up everywhere: choose the k highest-paying tasks but report them in arrival order, choose the k longest log lines but stream them in chronological order, choose the k busiest endpoints but render them alphabetically. Every one of those reduces to "select by attribute A, restore by attribute B" — the exact skill this problem teaches.

The Core Insight#

A subsequence preserves the original index order. Therefore the problem decomposes into two independent steps:

1. Identify the k indices whose values give the maximum sum.
2. Output those values in increasing index order.

A min-heap of size k indexed by (value, index) is the natural data structure. After scanning the array we have the k chosen indices; we then sort the surviving entries by index and emit their values.

Visual Dry Run#

For nums = [2, 1, 3, 3], k = 2, using a min-heap of size 2 over (value, index):

Final heap contents: (3, 2) and (3, 3). Sort by index -> indices 2 and 3 -> output [3, 3].

Solution (Optimal)#

import heapq
from typing import List
 
class Solution:
    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:
        # Min-heap of (value, index); cap at size k
        heap = []
        for i, v in enumerate(nums):
            heapq.heappush(heap, (v, i))
            if len(heap) > k:
                heapq.heappop(heap)
 
        # Sort surviving entries by original index, return values
        heap.sort(key=lambda x: x[1])
        return [v for v, _ in heap]

var maxSubsequence = function(nums, k) {
    // Pair value with index, sort by value descending, take top-k
    const indexed = nums.map((v, i) => [v, i]);
    indexed.sort((a, b) => b[0] - a[0]);
    const top = indexed.slice(0, k);
 
    // Restore original order by sorting on index
    top.sort((a, b) => a[1] - b[1]);
    return top.map(p => p[0]);
};

Time: O(n log k) for the heap approach, O(n log n) for the sort approach. Space: O(k) for the heap, O(n) for the indexed pairs.

Why the Heap Wins on Streaming Inputs#

The sort approach materialises the entire indexed array — fine for n = 1000 but wasteful when n is in the millions. The heap version only ever holds k entries in memory and is the natural answer for streaming inputs. Mention this distinction in the interview to show you understand when each approach shines.

Common Mistakes#

• Returning the heap contents directly without restoring original order — fails the subsequence property.
• Using a max-heap and trying to keep the smallest-k; you actually want a min-heap to evict the smallest of the top-k easily.
• Forgetting tie-breaking; if two values are equal, the index keeps the comparison total and stable.
• Treating duplicates as one element and returning fewer than k items.
• Sorting the whole array up front when only the top k matter — fine for small n but misses the streaming pattern.

Interview Tips#

• State the two-phase plan out loud: "Select by value, then restore by index."
• Pick the heap approach if the interviewer hints at streaming or large inputs.
• Mention quickselect as the deterministic O(n) alternative for selection.
• Always pair values with indices when ties are possible — naked numbers cannot tell you where they came from.
• Walk through one duplicate example to prove your code does not deduplicate.

Follow-up Questions#

• What if k can change at query time? Maintain a sorted structure or recompute on demand.
• What if you need the lexicographically smallest subsequence among ties? Use a stack-based monotonic approach (LeetCode 402 style).
• How would you parallelise this across shards? Compute local top-k per shard, then merge.
• What if values are huge but k is tiny? The heap approach still uses O(k) extra space — perfect.
• Can you return the answer in O(n) deterministic time? Yes, using introselect or median-of-medians for the selection step.

Key Takeaways#

• LeetCode 2099 is a two-phase problem: select the top-k by value, then restore original index order for the subsequence guarantee.
• A min-heap of size k holds the running top-k in O(n log k) time and O(k) space.
• Pair every value with its original index in the heap so duplicates stay disambiguated and order can be restored.
• For streaming inputs prefer the heap approach; for small static arrays a simple sort is equally correct.
• Quickselect gives a deterministic O(n) alternative when only the unsorted set of top-k is needed.
• Decoupling selection criterion from output ordering is a recurring FAANG pattern that surfaces in logging, ranking, and scheduling questions.
• Always restore order after selection; emitting heap contents directly violates the subsequence property and is the most common mistake on this question.