LeetCode Daily Challenge-2099. Find Subsequence of Length K With the Largest Sum(Easy)

• LeetCode Link
• Topics: Array,Hash Table,Sorting,Heap (Priority Queue)
• Date: 28th June 2025

Problem Overview

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.

Key Constraint: 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.

Examples

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.

The Challenge

The tricky part of this problem is that we need to:

1. Select the k largest elements to maximize the sum
2. Maintain their original relative order in the final subsequence

Simply sorting and taking the first k elements won't work because it would break the ordering constraint.

Solution Approach

To achieve the largest possible sum of a subsequence of length k, it makes sense to select the k largest elements from the array. However, we need a strategy to preserve their original order.

Strategy Breakdown

1. Track indices with values: Pair each element with its original index
2. Sort by value: Sort these pairs by value in descending order
3. Select top k: Take the k largest elements
4. Restore original order: Sort the selected elements by their original indices
5. Extract values: Return just the values in their original order

Code Implementation

Here's the solution with detailed comments:

class Solution:
    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:
        # Step 1: Pair each number with its original index
        # This allows us to track where each element came from
        nums_with_indices = [(num, i) for i, num in enumerate(nums)]

        # Step 2: Sort by value in descending order
        # We want the largest values first to maximize our sum
        nums_with_indices.sort(key=lambda x: -x[0])

        # Step 3: Take the top k largest values
        # These are the k elements that will give us the maximum sum
        top_k = nums_with_indices[:k]

        # Step 4: Sort by original index to maintain relative order
        # This ensures our subsequence maintains the original ordering
        top_k.sort(key=lambda x: x[1])

        # Step 5: Extract just the values and return
        return [num for num, _ in top_k]

Step-by-Step Walkthrough

Let's trace through Example 1: nums = [2,1,3,3], k = 2

1. Create pairs: [(2,0), (1,1), (3,2), (3,3)]
2. Sort by value desc: [(3,2), (3,3), (2,0), (1,1)]
3. Take top 2: [(3,2), (3,3)]
4. Sort by index: [(3,2), (3,3)] (already sorted)
5. Extract values: [3, 3]

For Example 2: nums = [-1,-2,3,4], k = 3

1. Create pairs: [(-1,0), (-2,1), (3,2), (4,3)]
2. Sort by value desc: [(4,3), (3,2), (-1,0), (-2,1)]
3. Take top 3: [(4,3), (3,2), (-1,0)]
4. Sort by index: [(-1,0), (3,2), (4,3)]
5. Extract values: [-1, 3, 4]

Algorithm Analysis

Time Complexity: O(n log n)

• Creating pairs: O(n)
• Sorting by value: O(n log n)
• Taking top k: O(1)
• Sorting by index: O(k log k)
• Extracting values: O(k)
• Overall: O(n log n) dominates

Space Complexity: O(n)

• We store n pairs of (value, index)
• The sorting operations use additional space

Key Insights

1. Greedy Approach: The problem is not about subsequences in the traditional sense, but rather about selecting the largest elements while maintaining their original order.

2. Index Tracking: The crucial insight is pairing each value with its original index. This allows us to sort by value first, then restore the original order.

3. Two-Stage Sorting: We sort twice - first by value to find the k largest elements, then by index to maintain the original sequence order.

Alternative Approaches

While the above solution is clean and intuitive, there are other approaches:

1. Using nth_element: For better average case performance, you could use nth_element to find the k largest elements without fully sorting.

2. Heap-based approach: Use a min-heap of size k to track the k largest elements while preserving indices.

Common Pitfalls

1. Forgetting to preserve order: Simply sorting and taking the first k elements breaks the subsequence property.

2. Not handling duplicates correctly: When there are duplicate values, we need to be careful about which instances to include.

3. Misunderstanding subsequence: Remember that subsequence preserves relative order, unlike subset which doesn't.

Conclusion

The challenge was recognizing that it could be solved with a greedy approach rather than a brute-force subsequence generation. This problem beautifully demonstrates how pairing data with metadata (in this case, indices) can help solve ordering constraints elegantly.

The key takeaway is that when you need to select optimal elements while preserving some original property (like order), consider tracking that property alongside your data throughout the selection process.