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 length k that has the largest sum. If there are multiple subsequences, return the one with the largest sum and smallest lexicographical order.

Clarifying Questions

  1. Can the input array nums contain negative numbers?
    • Yes, the array can contain negative numbers.
  2. Is the order of elements in the output subsequence important?
    • Yes, the output should maintain the original order of elements as they appear in nums.
  3. What are the constraints on the values of k and the length of nums?
    • Typically, 1 <= k <= length of nums <= 1000 and -10^5 <= nums[i] <= 10^5.
  4. Is it guaranteed that a subsequence of length k always exists?
    • Yes, since 1 <= k <= length of nums.

Strategy

  1. Select Top k Elements: Identify the k largest elements in the array.
  2. Maintain Order: Once we have those k largest elements, traverse the array and select them in order as they appear.
  3. Handling Ties: If multiple elements have the same value, ensure we maintain their order from the input to manage ties correctly.

Code

import java.util.*;

public class Solution {
    public int[] maxSubsequence(int[] nums, int k) {
        int n = nums.length;
        
        // Step 1: Create an array of index and values from nums
        int[][] numWithIndex = new int[n][2];
        for (int i = 0; i < n; i++) {
            numWithIndex[i][0] = nums[i];
            numWithIndex[i][1] = i;
        }
        
        // Step 2: Sort the array based on values in descending order
        Arrays.sort(numWithIndex, (a, b) -> b[0] - a[0]);
        
        // Step 3: Collect the indices of the top k elements
        int[] indices = new int[k];
        for (int i = 0; i < k; i++) {
            indices[i] = numWithIndex[i][1];
        }
        
        // Step 4: Sort the indices to maintain the order of appearance
        Arrays.sort(indices);
        
        // Step 5: Construct the result based on sorted indices
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = nums[indices[i]];
        }
        
        return result;
    }
    
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {3, 4, 3, 3};
        int k = 2;
        int[] result = sol.maxSubsequence(nums, k);
        System.out.println(Arrays.toString(result));  // Output: [4, 3]
    }
}

Explanation

  1. Step 1: Create pairs of numbers and their indices from nums.
  2. Step 2: Sort the pairs in descending order based on the number values.
  3. Step 3: Extract the indices of the top k numbers.
  4. Step 4: Sort these indices to restore the original relative order among the selected k elements.
  5. Step 5: Finally, construct the resultant subsequence according to these sorted indices.

Time Complexity

Thus, the time complexity for the entire solution is O(n log n), considering k is relatively small compared to n.

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