LeetCode 2099 - Find Subsequence of Length K With the Largest Sum

The problem asks us to find a subsequence of length k from a given integer array nums such that the sum of the elements in the subsequence is maximized.

leetcodeeasyarrayhash-tablesortingheap-(priority-queue)

LeetCode Problem 2099

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Sorting, Heap (Priority Queue)

Solution

Problem Understanding

The problem asks us to find a subsequence of length k from a given integer array nums such that the sum of the elements in the subsequence is maximized. A subsequence is defined as a sequence that can be obtained from the original array by deleting zero or more elements without changing the order of the remaining elements. The input consists of an array nums of length up to 1000, with elements ranging from -10^5 to 10^5, and an integer k which is guaranteed to be between 1 and the length of the array.

The expected output is an array of length k that forms a subsequence with the largest sum. Importantly, multiple valid answers can exist if there are duplicate elements or different orderings that result in the same sum.

Key edge cases include arrays with negative numbers, arrays where multiple subsequences yield the same sum, and arrays where k equals the length of the array or is 1. The constraints allow solutions with time complexity up to roughly O(n log n), given n <= 1000.

Approaches

A brute-force approach would involve generating all possible subsequences of length k, computing their sums, and returning the one with the largest sum. While this guarantees correctness, the number of subsequences grows combinatorially as C(n, k) = n! / (k! * (n-k)!). For even modest values of n and k, this becomes computationally infeasible.

The key insight for an optimal approach is that the subsequence with the largest sum must consist of the k largest numbers from nums, but to maintain the subsequence property, their original order in nums must be preserved. Therefore, the strategy is to first identify the k largest numbers and then reconstruct them in the order they appear in the original array.

We can use a heap or sorting to efficiently find the k largest numbers, and then iterate through the array to build the subsequence by selecting numbers in their original order.

Approach Time Complexity Space Complexity Notes
Brute Force O(C(n, k) * k) O(C(n, k)) Generate all subsequences of length k and compute sums
Optimal O(n log k) or O(n log n) O(k) Use a heap or sort to find k largest elements, then reconstruct subsequence

Algorithm Walkthrough

  1. Pair values with indices: Create a list of tuples where each tuple contains an element from nums and its index. This allows us to reconstruct the subsequence in the original order after selecting the largest elements.
  2. Select k largest elements: Use a min-heap of size k to keep track of the k largest elements as we iterate through the array. Alternatively, sort the array of tuples by value in descending order and take the first k elements.
  3. Sort by original index: To preserve the order in the original array, sort the selected k elements by their original indices.
  4. Extract values: Return the values of the sorted elements as the final subsequence.

Why it works: By choosing the k largest numbers, we guarantee the sum is maximized. Sorting by original indices preserves the subsequence property, so the resulting array is valid.

Python Solution

from typing import List

class Solution:
    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:
        # Step 1: Pair each number with its index
        indexed_nums = [(num, i) for i, num in enumerate(nums)]
        
        # Step 2: Find the k largest elements based on value
        indexed_nums.sort(key=lambda x: -x[0])
        top_k = indexed_nums[:k]
        
        # Step 3: Sort the selected k elements by their original index
        top_k.sort(key=lambda x: x[1])
        
        # Step 4: Extract the values to form the subsequence
        return [num for num, _ in top_k]

The implementation first pairs each number with its index, allowing us to reconstruct the subsequence in order. Sorting the pairs by value identifies the k largest numbers. Sorting these top k elements by their original indices ensures the subsequence respects the original order. Finally, we extract and return just the values.

Go Solution

import "sort"

func maxSubsequence(nums []int, k int) []int {
    type pair struct {
        val, idx int
    }

    n := len(nums)
    indexedNums := make([]pair, n)
    for i := 0; i < n; i++ {
        indexedNums[i] = pair{nums[i], i}
    }

    // Step 2: Sort by value descending
    sort.Slice(indexedNums, func(i, j int) bool {
        return indexedNums[i].val > indexedNums[j].val
    })
    topK := indexedNums[:k]

    // Step 3: Sort top k by original index
    sort.Slice(topK, func(i, j int) bool {
        return topK[i].idx < topK[j].idx
    })

    // Step 4: Extract values
    result := make([]int, k)
    for i := 0; i < k; i++ {
        result[i] = topK[i].val
    }
    return result
}

In Go, we define a pair struct to track values and indices. Sorting is done with sort.Slice for both descending values and ascending indices. Slice manipulation and allocation are explicit but follow the same logic as the Python version.

Worked Examples

Example 1: nums = [2,1,3,3], k = 2

  1. Pair with indices: [(2,0), (1,1), (3,2), (3,3)]
  2. Sort by value descending: [(3,2), (3,3), (2,0), (1,1)]
  3. Take top 2: [(3,2), (3,3)]
  4. Sort by index: [(3,2), (3,3)]
  5. Extract values: [3,3]

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

  1. Pair: [(-1,0), (-2,1), (3,2), (4,3)]
  2. Sort by value: [(4,3), (3,2), (-1,0), (-2,1)]
  3. Top 3: [(4,3), (3,2), (-1,0)]
  4. Sort by index: [(-1,0), (3,2), (4,3)]
  5. Result: [-1,3,4]

Example 3: nums = [3,4,3,3], k = 2

  1. Pair: [(3,0),(4,1),(3,2),(3,3)]
  2. Sort by value: [(4,1),(3,0),(3,2),(3,3)]
  3. Top 2: [(4,1),(3,0)]
  4. Sort by index: [(3,0),(4,1)]
  5. Result: [3,4]

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting the array of size n dominates the runtime
Space O(n) Storing the indexed array requires O(n) space

Sorting is the main cost, and storing the index-value pairs incurs additional linear space.

Test Cases

# Provided examples
assert Solution().maxSubsequence([2,1,3,3], 2) == [3,3]  # largest sum 6
assert Solution().maxSubsequence([-1,-2,3,4], 3) == [-1,3,4]  # largest sum 6
assert Solution().maxSubsequence([3,4,3,3], 2) == [3,4]  # largest sum 7

# Edge cases
assert Solution().maxSubsequence([1], 1) == [1]  # single element
assert Solution().maxSubsequence([5,4,3,2,1], 5) == [5,4,3,2,1]  # k equals array length
assert Solution().maxSubsequence([-5,-2,-3,-1], 2) == [-1,-2]  # all negative numbers
assert Solution().maxSubsequence([1,2,2,3], 3) == [2,2,3]  # duplicates
assert Solution().maxSubsequence([10,9,8,7,6], 1) == [10]  # k = 1
Test Why
[2,1,3,3], 2 Normal case with duplicate largest numbers
[-1,-2,3,4], 3 Mix of negative and positive numbers
[3,4,3,3], 2 Multiple valid subsequences
[1], 1 Single element edge case
[5,4,3,2,1], 5 k equals array length
[-5,-2,-3,-