Skip to main content
Talentd

Maximum Elegance of a K-Length Subsequence - Solution & Explanation

HardArrayHash TableStackGreedy16 min read
Practice this problem

Problem Statement

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 <= 105
  • items[i].length == 2
  • items[i][0] == profiti
  • items[i][1] == categoryi
  • 1 <= profiti <= 109
  • 1 <= categoryi <= n
  • 1 <= k <= n

Approach Overview

Problem 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 1: Brute Force Approach

The brute force approach involves trying all possible solutions to find the correct one. This typically involves iterating over all possible combinations or permutations to check each possible solution.

This approach might be clear and simple, but it's often inefficient for large inputs due to its high time complexity.

This C code contains a simple placeholder function for the brute force solution. Replace the logic with the specific brute force solution code.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * m)
Space Complexity: O(1) for in-place computation.

Try this approach in the editor →

Approach 2: Optimized Approach Using Dynamic Programming

This approach uses dynamic programming (DP) to solve the problem efficiently by breaking it down into simpler subproblems and storing the results of these subproblems to avoid redundant computations.

DP is especially useful for problems that exhibit overlapping subproblems and optimal substructure properties.

This C code provides a structure for implementing an optimized solution using dynamic programming. The actual DP logic needs to be implemented where indicated.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(n) for the DP array.

Try this approach in the editor →

Approach 3: Greedy

We can sort all items by profit from large to small. First choose the first k items and calculate the total profit tot. Use a hash table vis to record the categories of these k items, use a stack dup to record the profits of the repeated categories in order, and use a variable ans to record the current maximum elegance.

Next, we consider starting from the k+1 item. If its category is already in vis, it means that if we choose this category, the number of different categories will not increase, so we can skip this item directly. If there is no duplicate category before, we can also skip this item directly. Otherwise, we can consider replacing the top item of dup stack (the item with the minimum profit in the duplicate category) with the current item, which can increase the total profit by p - dup.pop() and increase the number of different categories by 1, so we can update tot and ans.

Finally, we return ans.

The time complexity is O(n times log n) and the space complexity is O(n), where n is the number of items.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force Approach

Time Complexity: O(n * m)
Space Complexity: O(1) for in-place computation.

Optimized Approach Using Dynamic Programming

Time Complexity: O(n)
Space Complexity: O(n) for the DP array.

Greedy—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force EnumerationO(C(n, k) * k)O(k)Conceptual baseline or very small input sizes
Greedy with Sorting + Min HeapO(n log n)O(n)General optimal solution balancing profit and category diversity

Video Solution

2813. Maximum Elegance of a K-Length Subsequence || Weekly Contest 357 || Leetcode || Hindi • Ashish Kumar • 532 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Maximum Elegance of a K-Length Subsequence easy or hard?
Maximum Elegance of a K-Length Subsequence is labeled Hard on LeetCode with an acceptance rate around 28%. The difficulty comes from recognizing the profit vs. diversity tradeoff and implementing the greedy replacement strategy with a heap.
Maximum Elegance of a K-Length Subsequence Python/Java solution
Most implementations follow the same greedy pattern across languages. Sort items by profit, maintain a set or hash map for categories, and store duplicate-category profits in a min heap. Python typically uses heapq, while Java uses PriorityQueue. Both achieve O(n log n) time complexity.
How to solve Maximum Elegance of a K-Length Subsequence in O(n log n)?
Sort items by profit in descending order and select the first k items to maximize initial profit. Track duplicate-category selections using a min heap. Then scan remaining items and replace the smallest duplicate-profit item whenever you encounter a new category. Each replacement increases the distinct category count and may improve the elegance score.
What is the best approach for Maximum Elegance of a K-Length Subsequence?
The most effective solution uses a greedy strategy with sorting and a min heap. First sort items by profit and take the top k items. Track duplicate-category items in a heap so they can be replaced later with items from new categories. This allows increasing the distinct category bonus while minimizing profit loss, achieving O(n log n) time complexity.
Is Maximum Elegance of a K-Length Subsequence asked at Google/Amazon/Meta?
Problems combining greedy selection with heaps and category counting frequently appear in interviews at companies like Amazon, Google, and Meta. Variants involving maximizing a score with tradeoffs between value and diversity are especially common in senior-level algorithm interviews.
What data structure is used in Maximum Elegance of a K-Length Subsequence?
The optimal solution relies on several core structures: sorting for ordering items by profit, a hash table to track category frequencies, and a min heap (priority queue) to efficiently remove the smallest duplicate-category profit when introducing a new category.
What is the time complexity of Maximum Elegance of a K-Length Subsequence?
The optimal approach runs in O(n log n) time. Sorting the items by profit costs O(n log n), and heap operations for replacing duplicate-category items add O(log k) per operation. Space complexity is O(n) for tracking categories and maintaining the heap.

Ready to solve this problem?

Practice Maximum Elegance of a K-Length Subsequence with our built-in code editor and test cases.

Practice on FleetCode
Previous

IPO