LeetCode 3684 - Maximize Sum of At Most K Distinct Elements

This problem requires selecting at most k distinct elements from a given array of positive integers nums such that their sum is maximized. The result must be returned as a list sorted in strictly descending order.

leetcodeeasyarrayhash-tablegreedysorting

LeetCode Problem 3684

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Greedy, Sorting

Solution

Problem Understanding

This problem requires selecting at most k distinct elements from a given array of positive integers nums such that their sum is maximized. The result must be returned as a list sorted in strictly descending order.

The input nums represents a collection of numbers from which we can pick a subset. Each number can only contribute once to the chosen subset since the selection must be distinct. The integer k restricts the maximum number of elements we can select, but we may pick fewer than k if there are not enough unique numbers.

The constraints are relatively small: 1 <= nums.length <= 100 and each number is up to 10^9. This indicates that we do not need a highly optimized solution; a simple O(n log n) approach is acceptable. The constraints guarantee that k is at least 1 and at most nums.length, so we always have a valid upper bound.

Edge cases to consider include arrays where all numbers are the same, k larger than the number of unique numbers, or nums already being sorted in descending order. These could trip up a naive implementation that either does not enforce uniqueness or blindly takes the first k numbers.

Approaches

Brute Force

The brute-force approach would involve generating all subsets of nums of size up to k, filtering for distinct elements, computing their sums, and selecting the subset with the maximum sum. While correct, this approach is extremely inefficient because the number of subsets grows exponentially with the array size, making it impractical even for the given constraints. It also introduces unnecessary complexity in handling duplicates and enforcing distinctness manually.

Optimal Approach

The key insight is that to maximize the sum, we should always pick the largest unique numbers. This allows us to simplify the problem drastically. First, we remove duplicates to get the distinct numbers. Then we sort them in descending order, and finally, select the first k elements. This guarantees the maximum sum while satisfying the uniqueness requirement. Sorting is the dominant operation, giving us an efficient O(n log n) solution.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(n) Generate all subsets and filter for distinct elements, too slow
Optimal O(n log n) O(n) Deduplicate, sort descending, select top k elements

Algorithm Walkthrough

  1. Deduplicate nums: Use a set to remove duplicates and retain only unique elements. This ensures all chosen elements are distinct.
  2. Sort in descending order: Convert the set back to a list and sort it in descending order. Sorting allows easy selection of the largest elements first.
  3. Select top k elements: Slice the sorted list to take at most k elements. This handles cases where k exceeds the number of unique elements.
  4. Return the result: The sliced list is already in strictly descending order and contains at most k distinct elements.

Why it works: The algorithm guarantees correctness because choosing the largest unique numbers ensures the sum is maximized. Sorting enforces descending order automatically, and slicing guarantees the limit of k elements is respected. The combination of deduplication and sorting preserves the invariant that no duplicates exist and the sum is maximal.

Python Solution

from typing import List

class Solution:
    def maxKDistinct(self, nums: List[int], k: int) -> List[int]:
        # Step 1: Deduplicate using a set
        unique_nums = set(nums)
        
        # Step 2: Convert to list and sort descending
        sorted_unique = sorted(unique_nums, reverse=True)
        
        # Step 3: Take at most k elements
        result = sorted_unique[:k]
        
        return result

This Python implementation follows the optimal algorithm directly. We first remove duplicates with set(nums). Sorting in descending order ensures that the largest numbers appear first. Finally, slicing with [:k] guarantees that we select at most k elements. The resulting list is returned as required by the problem.

Go Solution

import "sort"

func maxKDistinct(nums []int, k int) []int {
    // Step 1: Deduplicate using a map
    uniqueMap := make(map[int]bool)
    for _, num := range nums {
        uniqueMap[num] = true
    }
    
    // Step 2: Convert map keys to slice
    uniqueNums := make([]int, 0, len(uniqueMap))
    for num := range uniqueMap {
        uniqueNums = append(uniqueNums, num)
    }
    
    // Step 3: Sort descending
    sort.Slice(uniqueNums, func(i, j int) bool {
        return uniqueNums[i] > uniqueNums[j]
    })
    
    // Step 4: Take at most k elements
    if len(uniqueNums) > k {
        uniqueNums = uniqueNums[:k]
    }
    
    return uniqueNums
}

In Go, we use a map to deduplicate nums. Sorting is done with sort.Slice and a custom comparator for descending order. We handle the slice length carefully to ensure we do not exceed k. Unlike Python, we explicitly check the length because slices in Go cannot be sliced beyond their current length.

Worked Examples

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

Step Operation Result
1 Deduplicate {84, 93, 100, 77, 90}
2 Sort descending [100, 93, 90, 84, 77]
3 Take top k=3 [100, 93, 90]

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

Step Operation Result
1 Deduplicate {84, 93, 100, 77}
2 Sort descending [100, 93, 84, 77]
3 Take top k=3 [100, 93, 84]

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

Step Operation Result
1 Deduplicate {1, 2}
2 Sort descending [2, 1]
3 Take top k=6 [2, 1]

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Deduplicating takes O(n), sorting the unique elements dominates with O(n log n)
Space O(n) Set/map storage for unique elements requires up to O(n) space

The algorithm is efficient for the given constraints, as n is at most 100. Deduplication and sorting are straightforward and do not introduce hidden costs.

Test Cases

# Provided examples
assert Solution().maxKDistinct([84,93,100,77,90], 3) == [100,93,90]  # Example 1
assert Solution().maxKDistinct([84,93,100,77,93], 3) == [100,93,84]  # Example 2
assert Solution().maxKDistinct([1,1,1,2,2,2], 6) == [2,1]  # Example 3

# Edge cases
assert Solution().maxKDistinct([5,5,5,5], 1) == [5]  # Only one unique element
assert Solution().maxKDistinct([10,20,30], 5) == [30,20,10]  # k exceeds unique elements
assert Solution().maxKDistinct([1], 1) == [1]  # Single element array
assert Solution().maxKDistinct([3,1,4,1,5,9,2,6,5], 4) == [9,6,5,4]  # Mixed duplicates
Test Why
Single unique element repeated Ensures deduplication works
k larger than unique elements Ensures slicing handles fewer elements than k
Single-element array Minimal input size validation
Mixed duplicates General correctness and ordering

Edge Cases

One edge case occurs when all numbers are identical, such as [5,5,5,5]. Here, deduplication reduces the array to a single number, and selecting k elements still only returns one value. The algorithm handles this by deduplicating first and then slicing safely.

Another edge case is when k is larger than the number of unique numbers, such as [10,20,30] with k=5. The algorithm only returns the available unique numbers, preventing any out-of-bounds error or need for padding.

A third edge case is minimal input, where nums contains just one number and k=1. The algorithm handles this naturally: deduplication leaves the same number, sorting has no effect, and slicing returns the single element. This ensures the function works at the lower boundary of input constraints.