algoadvance

Leetcode 2099. Find Subsequence of Length K With the Largest Sum

Problem Statement:

Given an integer array nums and an integer k, return the subsequence of nums (not necessarily contiguous) of length k that has the largest sum. If there are multiple answers, return any of them.

Clarifying Questions:

  1. Can k be larger than the length of the nums array?
    • No, k will always be less than or equal to the length of the nums array.
  2. Can nums contain negative numbers?
    • Yes, nums can contain negative numbers.
  3. Do we need to maintain the order of elements in the subsequence as they appeared in the original array?
    • Yes, the order of the elements in the chosen subsequence should be maintained as in the original array.

Strategy:

  1. Sort with Indices: Create a list of pairs, where each pair is (element, index) from the nums array.
  2. Find Top K Elements: Sort this list based on the element values in descending order.
  3. Extract Indices: Extract the indices of the top k elements.
  4. Reconstruct Subsequence: Sort these indices to maintain the order and then extract the corresponding elements from nums.

Code:

#include <vector>
#include <algorithm>
#include <iostream>

std::vector<int> maxSubsequence(std::vector<int>& nums, int k) {
    // Step 1: Pair each element with its index
    std::vector<std::pair<int, int>> nums_with_indices;
    for (int i = 0; i < nums.size(); ++i) {
        nums_with_indices.push_back({nums[i], i});
    }

    // Step 2: Sort the pairs by their values in descending order
    std::sort(nums_with_indices.begin(), nums_with_indices.end(), 
        [](const std::pair<int, int>& a, const std::pair<int, int>& b) {
            return a.first > b.first;
        }
    );

    // Step 3: Extract the indices of the top k elements
    std::vector<int> indices;
    for (int i = 0; i < k; ++i) {
        indices.push_back(nums_with_indices[i].second);
    }

    // Step 4: Sort the indices to maintain the original order
    std::sort(indices.begin(), indices.end());

    // Step 5: Extract the elements using the sorted indices
    std::vector<int> result;
    for (int index : indices) {
        result.push_back(nums[index]);
    }

    return result;
}

// Example usage
int main() {
    std::vector<int> nums = {3, 4, 3, 3};
    int k = 2;
    std::vector<int> result = maxSubsequence(nums, k);
    
    // Output the result
    for (int num : result) {
        std::cout << num << " ";
    }

    return 0;
}

Time Complexity:

  1. Pairing Elements and Indices: This takes O(n) time, where n is the number of elements in nums.
  2. Sorting: Sorting the pairs takes O(n log n).
  3. Extracting Top K Indices: This takes O(k).
  4. Sorting Indices: Sorting k indices takes O(k log k).
  5. Extracting Elements: This takes O(k).

Overall, the dominant factor is the sorting step, so the time complexity is O(n log n).

This approach ensures that we correctly find the subsequence of length k with the largest sum while maintaining the order of elements as in the original nums array.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI