Watch 7 video solutions for Maximum Elegance of a K-Length Subsequence, a hard level problem involving Array, Hash Table, Stack. This walkthrough by Ashish Kumar has 510 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a 0-indexed 2D integer array items of length n and an integer k.
items[i] = [profiti, categoryi], where profiti and categoryi denote the profit and category of the ith item respectively.
Let's define the elegance of a subsequence of items as total_profit + distinct_categories2, where total_profit is the sum of all profits in the subsequence, and distinct_categories is the number of distinct categories from all the categories in the selected subsequence.
Your task is to find the maximum elegance from all subsequences of size k in items.
Return an integer denoting the maximum elegance of a subsequence of items with size exactly k.
Note: A subsequence of an array is a new array generated from the original array by deleting some elements (possibly none) without changing the remaining elements' relative order.
Example 1:
Input: items = [[3,2],[5,1],[10,1]], k = 2 Output: 17 Explanation: In this example, we have to select a subsequence of size 2. We can select items[0] = [3,2] and items[2] = [10,1]. The total profit in this subsequence is 3 + 10 = 13, and the subsequence contains 2 distinct categories [2,1]. Hence, the elegance is 13 + 22 = 17, and we can show that it is the maximum achievable elegance.
Example 2:
Input: items = [[3,1],[3,1],[2,2],[5,3]], k = 3 Output: 19 Explanation: In this example, we have to select a subsequence of size 3. We can select items[0] = [3,1], items[2] = [2,2], and items[3] = [5,3]. The total profit in this subsequence is 3 + 2 + 5 = 10, and the subsequence contains 3 distinct categories [1,2,3]. Hence, the elegance is 10 + 32 = 19, and we can show that it is the maximum achievable elegance.
Example 3:
Input: items = [[1,1],[2,1],[3,1]], k = 3 Output: 7 Explanation: In this example, we have to select a subsequence of size 3. We should select all the items. The total profit will be 1 + 2 + 3 = 6, and the subsequence contains 1 distinct category [1]. Hence, the maximum elegance is 6 + 12 = 7.
Constraints:
1 <= items.length == n <= 105items[i].length == 2items[i][0] == profitiitems[i][1] == categoryi1 <= profiti <= 1091 <= categoryi <= n 1 <= k <= nProblem Overview: You are given items where each item has a profit and a category. Choose exactly k items to maximize total_profit + (distinct_categories)^2. The challenge is balancing raw profit with category diversity because adding a new category increases the squared bonus.
Approach 1: Brute Force Enumeration (Exponential Time)
Generate every possible subsequence of length k. For each candidate set, compute the sum of profits and count distinct categories using a hash set. The elegance score is then profit_sum + unique_categories^2, and you track the maximum across all combinations. This approach requires iterating through C(n, k) possibilities, which becomes infeasible even for moderate n. Time complexity is O(C(n, k) * k) because each subset requires counting categories, and space complexity is O(k) for tracking the current subset and category set. This approach mainly serves as a correctness baseline.
Approach 2: Greedy with Sorting and Heap (O(n log n))
Sort items by profit in descending order using sorting. First pick the top k items to maximize the base profit. While selecting these, track category frequencies with a hash table. If multiple items share the same category, push the smaller-profit duplicates into a min-heap. The heap represents candidates you can replace later.
Next iterate over the remaining items. Whenever you encounter an item from a new category, you can increase the distinct category count. If the heap contains a duplicate-category item, remove the smallest-profit duplicate and replace it with this new-category item. This slightly reduces profit but increases the category diversity bonus. Maintain the current profit sum and compute profit + distinct^2 after each change.
The key insight: the best candidates to swap out are duplicate-category items with the smallest profits. A min-heap makes these replacements efficient. Sorting costs O(n log n), and heap operations add another O(n log k), so the overall complexity is O(n log n) time with O(n) space.
Recommended for interviews: Interviewers expect the greedy + heap approach. Brute force demonstrates understanding of the scoring formula, but the optimized solution shows you can reason about profit tradeoffs and maintain candidates efficiently with sorting, hashing, and priority queues.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(C(n, k) * k) | O(k) | Conceptual baseline or very small input sizes |
| Greedy with Sorting + Min Heap | O(n log n) | O(n) | General optimal solution balancing profit and category diversity |