Maximize Sum of At Most K Distinct Elements - Solution & Explanation

Problem Overview: You are given an array of integers and a number k. The goal is to select at most k distinct elements such that their sum is as large as possible. Duplicate values cannot be counted multiple times, so the solution must ensure uniqueness while maximizing the total.

Approach 1: Brute Force with Distinct Tracking (Exponential Time)

The most direct idea is to try every possible subset of elements and keep only those containing at most k distinct values. For each valid subset, compute the sum and track the maximum. While this guarantees correctness, the number of subsets grows exponentially with the array size. Time complexity becomes O(2^n) and space complexity is O(n) due to recursion or subset storage. This approach is mainly useful for understanding the constraints but is impractical for real input sizes.

Approach 2: Hash Set + Sorting (Greedy) (O(n log n))

The key observation is that if you want the maximum possible sum with distinct elements, you should always choose the largest available unique values first. Start by removing duplicates using a hash set. This guarantees each number is counted once. Convert the set back to a list and sort it in descending order using a standard sorting algorithm. Then iterate through the sorted values and add the top k elements to the sum. The sorting step dominates the complexity, giving O(n log n) time and O(n) space.

This approach combines ideas from array processing and hash table deduplication. The greedy step works because larger numbers always contribute more to the final sum, so selecting the largest unique values first is optimal.

Approach 3: Hash Set + Max Heap (O(n log n))

Another option is to insert distinct values into a max heap instead of sorting the entire array. After removing duplicates using a hash set, push the numbers into a heap and extract the largest element up to k times. Heap insertion and extraction both take O(log n), producing overall time complexity O(n log n) and space complexity O(n). This technique is useful when the data stream arrives incrementally or when you prefer priority queue operations instead of full sorting.

The greedy reasoning remains the same: always take the largest available distinct value first. This aligns with typical patterns seen in greedy optimization and sorting-based selection problems.

Recommended for interviews: The hash set + sorting approach is the most expected solution. It clearly demonstrates two key skills: eliminating duplicates efficiently and applying a greedy selection strategy after sorting. Mentioning the brute force method shows you understand the search space, but implementing the sorting-based approach proves you can reduce the problem to a clean O(n log n) solution.