Skip to content

3684. Maximize Sum of At Most K Distinct Elements

Description

You are given a positive integer array nums and an integer k.

Choose at most k elements from nums so that their sum is maximized. However, the chosen numbers must be distinct.

Return an array containing the chosen numbers in strictly descending order.

 

Example 1:

Input: nums = [84,93,100,77,90], k = 3

Output: [100,93,90]

Explanation:

The maximum sum is 283, which is attained by choosing 93, 100 and 90. We rearrange them in strictly descending order as [100, 93, 90].

Example 2:

Input: nums = [84,93,100,77,93], k = 3

Output: [100,93,84]

Explanation:

The maximum sum is 277, which is attained by choosing 84, 93 and 100. We rearrange them in strictly descending order as [100, 93, 84]. We cannot choose 93, 100 and 93 because the chosen numbers must be distinct.

Example 3:

Input: nums = [1,1,1,2,2,2], k = 6

Output: [2,1]

Explanation:

The maximum sum is 3, which is attained by choosing 1 and 2. We rearrange them in strictly descending order as [2, 1].

 

Constraints:

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 109
  • 1 <= k <= nums.length

Solutions

Solution 1: Sorting

We first sort the array \(\textit{nums}\), then iterate from the end to the beginning, selecting the largest \(k\) distinct elements. Since we require a strictly decreasing order, we skip duplicate elements during selection.

The time complexity is \(O(n \times \log n)\), where \(n\) is the length of the \(\textit{nums}\) array. Ignoring the space used for the answer, the space complexity is \(O(\log n)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def maxKDistinct(self, nums: List[int], k: int) -> List[int]:
        nums.sort()
        n = len(nums)
        ans = []
        for i in range(n - 1, -1, -1):
            if i + 1 < n and nums[i] == nums[i + 1]:
                continue
            ans.append(nums[i])
            k -= 1
            if k == 0:
                break
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
    public int[] maxKDistinct(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;
        List<Integer> ans = new ArrayList<>();
        for (int i = n - 1; i >= 0; --i) {
            if (i + 1 < n && nums[i] == nums[i + 1]) {
                continue;
            }
            ans.add(nums[i]);
            if (--k == 0) {
                break;
            }
        }
        return ans.stream().mapToInt(x -> x).toArray();
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> maxKDistinct(vector<int>& nums, int k) {
        ranges::sort(nums);
        int n = nums.size();
        vector<int> ans;
        for (int i = n - 1; ~i; --i) {
            if (i + 1 < n && nums[i] == nums[i + 1]) {
                continue;
            }
            ans.push_back(nums[i]);
            if (--k == 0) {
                break;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
func maxKDistinct(nums []int, k int) (ans []int) {
    slices.Sort(nums)
    n := len(nums)
    for i := n - 1; i >= 0; i-- {
        if i+1 < n && nums[i] == nums[i+1] {
            continue
        }
        ans = append(ans, nums[i])
        if k--; k == 0 {
            break
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
function maxKDistinct(nums: number[], k: number): number[] {
    nums.sort((a, b) => a - b);
    const ans: number[] = [];
    const n = nums.length;
    for (let i = n - 1; ~i; --i) {
        if (i + 1 < n && nums[i] === nums[i + 1]) {
            continue;
        }
        ans.push(nums[i]);
        if (--k === 0) {
            break;
        }
    }
    return ans;
}

Comments