2813. Maximum Elegance of a K-Length Subsequence LeetCode Solution
In this guide, you will get 2813. Maximum Elegance of a K-Length Subsequence LeetCode Solution with the best time and space complexity. The solution to Maximum Elegance of a K-Length Subsequence problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Maximum Elegance of a K-Length Subsequence
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.
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
Complexity Analysis
Time Complexity: O(\texttt{sort})
Space Complexity: O(n)
2813. Maximum Elegance of a K-Length Subsequence LeetCode Solution in C++
class Solution {
public:
long long findMaximumElegance(vector<vector<int>>& items, int k) {
long ans = 0;
long totalProfit = 0;
unordered_set<int> seenCategories;
stack<int> decreasingDuplicateProfits;
ranges::sort(items, greater<>());
for (int i = 0; i < k; i++) {
const int profit = items[i][0];
const int category = items[i][1];
totalProfit += profit;
if (seenCategories.contains(category))
decreasingDuplicateProfits.push(profit);
else
seenCategories.insert(category);
}
ans = totalProfit +
static_cast<long>(seenCategories.size()) * seenCategories.size();
for (int i = k; i < items.size(); ++i) {
const int profit = items[i][0];
const int category = items[i][1];
if (!seenCategories.contains(category) &&
!decreasingDuplicateProfits.empty()) {
// If this is a new category we haven't seen before, it's worth
// considering taking it and replacing the one with the least profit
// since it will increase the distinct_categories and potentially result
// in a larger total_profit + distinct_categories^2.
totalProfit -= decreasingDuplicateProfits.top(),
decreasingDuplicateProfits.pop();
totalProfit += profit;
seenCategories.insert(category);
ans = max(ans,
static_cast<long>(totalProfit +
static_cast<long>(seenCategories.size()) *
seenCategories.size()));
}
}
return ans;
}
}; /* code provided by PROGIEZ */
2813. Maximum Elegance of a K-Length Subsequence LeetCode Solution in Java
class Solution {
public long findMaximumElegance(int[][] items, int k) {
long ans = 0;
long totalProfit = 0;
Set<Integer> seenCategories = new HashSet<>();
Deque<Integer> decreasingDuplicateProfits = new ArrayDeque<>();
Arrays.sort(items, (a, b) -> Integer.compare(b[0], a[0]));
for (int i = 0; i < k; ++i) {
final int profit = items[i][0];
final int category = items[i][1];
totalProfit += profit;
if (seenCategories.contains(category))
decreasingDuplicateProfits.push(profit);
else
seenCategories.add(category);
}
ans = totalProfit + 1L * seenCategories.size() * seenCategories.size();
for (int i = k; i < items.length; ++i) {
final int profit = items[i][0];
final int category = items[i][1];
if (!seenCategories.contains(category) && !decreasingDuplicateProfits.isEmpty()) {
// If this is a new category we haven't seen before, it's worth
// considering taking it and replacing the one with the least profit
// since it will increase the distinct_categories and potentially result
// in a larger total_profit + distinct_categories^2.
totalProfit -= decreasingDuplicateProfits.pop();
totalProfit += profit;
seenCategories.add(category);
ans = Math.max(ans, totalProfit + 1L * seenCategories.size() * seenCategories.size());
}
}
return ans;
}
} // code provided by PROGIEZ
2813. Maximum Elegance of a K-Length Subsequence LeetCode Solution in Python
class Solution:
def findMaximumElegance(self, items: list[list[int]], k: int) -> int:
ans = 0
totalProfit = 0
seenCategories = set()
decreasingDuplicateProfits = []
items.sort(reverse=True)
for i in range(k):
profit, category = items[i]
totalProfit += profit
if category in seenCategories:
decreasingDuplicateProfits.append(profit)
else:
seenCategories.add(category)
ans = totalProfit + len(seenCategories)**2
for i in range(k, len(items)):
profit, category = items[i]
if category not in seenCategories and decreasingDuplicateProfits:
# If this is a new category we haven't seen before, it's worth
# considering taking it and replacing the one with the least profit
# since it will increase the distinct_categories and potentially result
# in a larger total_profit + distinct_categories^2.
totalProfit -= decreasingDuplicateProfits.pop()
totalProfit += profit
seenCategories.add(category)
ans = max(ans, totalProfit + len(seenCategories)**2)
return ans # code by PROGIEZ
