# Maximum Elegance of a K-Length Subsequence
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-elegance-of-a-k-length-subsequence)
Canonical: https://scaleengineer.com/dsa/problems/maximum-elegance-of-a-k-length-subsequence
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table, Stack, Heap (Priority Queue)
---
## Problem
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`

# Approaches
## Brute Force via Combinations
This approach involves generating every possible subsequence of size `k` from the `n` items. For each generated subsequence, we calculate its elegance, which is the sum of profits plus the square of the number of distinct categories. We keep track of the highest elegance value seen across all subsequences and return it as the final answer.
**Time:** O(C(n, k) * k). There are `C(n, k)` (n choose k) combinations. For each combination, we iterate through its `k` items to calculate the elegance. This is computationally infeasible for large `n`. · **Space:** O(k). The space is used to store the current subsequence being built and for the recursion stack, which will have a maximum depth of `k`.
**Pros:** Simple to understand and implement.; Correctness is guaranteed because it explores the entire solution space.
**Cons:** Extremely inefficient due to the combinatorial explosion of possibilities.; Guaranteed to result in a 'Time Limit Exceeded' (TLE) error for the given constraints.
### Explanation
The fundamental idea is to perform an exhaustive search. We can think of this as finding all combinations of `k` items from a set of `n`. A standard way to implement this is using a backtracking algorithm.

We define a recursive function that builds a subsequence. This function takes the starting index for selecting the next item and the subsequence built so far. When the subsequence reaches the desired size `k`, we process it: calculate its total profit and the number of distinct categories, compute the elegance, and update our global maximum. The recursion then backtracks to explore other possible combinations.

While this method is straightforward and guarantees correctness by checking every single possibility, its computational cost is prohibitively high. The number of combinations, given by `C(n, k)`, grows very rapidly with `n`, making this approach impractical for the problem's constraints.

```java
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    long maxElegance = 0;
    int n;
    int k;
    int[][] items;

    public long findMaximumElegance(int[][] items, int k) {
        this.n = items.length;
        this.k = k;
        this.items = items;
        findCombinations(0, new ArrayList<>());
        return maxElegance;
    }

    private void findCombinations(int start, List<int[]> currentSubsequence) {
        if (currentSubsequence.size() == k) {
            long currentProfit = 0;
            Set<Integer> categories = new HashSet<>();
            for (int[] item : currentSubsequence) {
                currentProfit += item[0];
                categories.add(item[1]);
            }
            long currentElegance = currentProfit + (long)categories.size() * categories.size();
            maxElegance = Math.max(maxElegance, currentElegance);
            return;
        }

        if (start >= n) {
            return;
        }

        // To avoid TLE, we can add a check, but the core logic is brute-force.
        // For every index i, we can either include items[i] or not.
        for (int i = start; i < n; i++) {
            currentSubsequence.add(items[i]);
            findCombinations(i + 1, currentSubsequence);
            currentSubsequence.remove(currentSubsequence.size() - 1); // backtrack
        }
    }
}
```
### Algorithm
- Initialize `max_elegance` to 0.
- Create a recursive helper function, say `generate_combinations(start_index, current_subsequence)`.
- **Base Case:** If the `current_subsequence` has size `k`:
    - Calculate its `total_profit` by summing the profits of its items.
    - Find the number of `distinct_categories` using a HashSet.
    - Compute the elegance: `total_profit + distinct_categories^2`.
    - Update `max_elegance` with the maximum value found so far.
    - Return.
- **Recursive Step:** Iterate from `i = start_index` to `n-1`:
    - Add `items[i]` to the `current_subsequence`.
    - Make a recursive call: `generate_combinations(i + 1, current_subsequence)`.
    - Remove `items[i]` from `current_subsequence` to backtrack and explore other combinations.
- Start the process by calling `generate_combinations(0, [])`.
- Return `max_elegance`.

## Greedy Approach with Sorting
This efficient approach uses a greedy strategy. The core insight is that to maximize elegance (`total_profit + distinct_categories^2`), we should start with the highest possible `total_profit`. We achieve this by initially selecting the `k` items with the greatest profits. This gives us a strong candidate solution. Then, we try to improve upon this solution by increasing the number of distinct categories. We can do this by swapping one of our selected items for an item we didn't select. The best trade is to swap out a low-profit item that has a duplicate category for a (potentially lower-profit) item that introduces a new category. This might decrease the `total_profit` slightly, but the gain from squaring a larger `distinct_categories` count can lead to a higher overall elegance.
**Time:** O(N log N). The dominant operation is sorting the `n` items, which takes `O(N log N)`. The subsequent passes through the array take a total of `O(N)` time. Thus, the overall time complexity is determined by the sort. · **Space:** O(k). The `seen_categories` set can store up to `k` distinct categories. The `duplicate_profits` stack can, in the worst case, store up to `k-1` profits. Therefore, the space required is proportional to `k`.
**Pros:** Highly efficient and optimal for the given constraints.; Cleverly balances the two competing components of elegance (profit and category diversity).; The use of a stack simplifies finding the best item to swap out.
**Cons:** The greedy logic is not immediately obvious and requires careful reasoning about the trade-off between profit and category diversity.
### Explanation
The algorithm proceeds in two main phases.

First, we sort the `items` array by profit in descending order. We then greedily select the top `k` items. This selection maximizes the `total_profit` component of elegance. While iterating through these top `k` items, we calculate their total profit, keep track of the categories we've seen in a `HashSet`, and store the profits of any items belonging to an already-seen category in a stack. This stack of `duplicate_profits` will be crucial for the next step.

After this first phase, we have an initial valid subsequence and its elegance, which we set as our current maximum.

Second, we iterate through the remaining `n-k` items. For each item, if it belongs to a category we haven't seen yet, we consider a swap. A swap is only beneficial if we can increase the number of distinct categories. To do this, we must remove an item from our current selection that belongs to a duplicate category (so removing it doesn't decrease our category count). To minimize the profit loss, we should remove the duplicate-category item with the lowest profit. Our `duplicate_profits` stack conveniently holds these profits, and since we processed the initial `k` items in descending order of profit, the profits pushed later (and thus at the top of the stack) are the smallest ones. If the stack is not empty, we perform the swap: pop a profit, update the `total_profit`, add the new category, and recalculate the elegance, updating our maximum if necessary. We continue this until we either run out of items to consider or have no more duplicate-category items to swap out.

```java
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

class Solution {
    public long findMaximumElegance(int[][] items, int k) {
        // Sort items by profit in descending order
        Arrays.sort(items, (a, b) -> b[0] - a[0]);

        long maxElegance = 0;
        long currentProfit = 0;
        Set<Integer> seenCategories = new HashSet<>();
        Stack<Integer> duplicateProfits = new Stack<>();

        // Phase 1: Greedily select the top k most profitable items
        for (int i = 0; i < k; i++) {
            int profit = items[i][0];
            int category = items[i][1];
            currentProfit += profit;
            if (seenCategories.contains(category)) {
                duplicateProfits.push(profit);
            } else {
                seenCategories.add(category);
            }
        }

        maxElegance = currentProfit + (long)seenCategories.size() * seenCategories.size();

        // Phase 2: Try to improve by swapping for new categories
        for (int i = k; i < items.length; i++) {
            if (duplicateProfits.isEmpty()) {
                break; // No more duplicate items to swap out
            }

            int profit = items[i][0];
            int category = items[i][1];

            if (!seenCategories.contains(category)) {
                // Swap out the least profitable duplicate item
                currentProfit = currentProfit - duplicateProfits.pop() + profit;
                seenCategories.add(category);
                
                // Recalculate elegance and update max
                long currentElegance = currentProfit + (long)seenCategories.size() * seenCategories.size();
                maxElegance = Math.max(maxElegance, currentElegance);
            }
        }

        return maxElegance;
    }
}
```
### Algorithm
- Sort the `items` array in descending order based on profit.
- Initialize `total_profit`, `max_elegance`, a `HashSet<Integer>` named `seen_categories`, and a `Stack<Integer>` named `duplicate_profits`.
- **Initial Selection:** Iterate through the first `k` items (the most profitable ones):
    - Add the item's profit to `total_profit`.
    - If the item's category is already in `seen_categories`, push its profit onto the `duplicate_profits` stack.
    - Otherwise, add the category to `seen_categories`.
- Calculate the initial `max_elegance` using the current `total_profit` and the size of `seen_categories`.
- **Iterative Improvement:** Iterate through the remaining items (from index `k` to `n-1`):
    - If `duplicate_profits` is empty, break the loop, as no beneficial swaps are possible.
    - If the current item's category is new (not in `seen_categories`):
        - Pop the smallest duplicate profit from the stack (this is the item we'll swap out).
        - Update `total_profit` by subtracting the popped profit and adding the current item's profit.
        - Add the new category to `seen_categories`.
        - Recalculate the elegance and update `max_elegance` if the new value is greater.
- Return `max_elegance`.

# Solutions
### Java

```java
class Solution {
public
  long findMaximumElegance(int[][] items, int k) {
    Arrays.sort(items, (a, b)->b[0] - a[0]);
    int n = items.length;
    long tot = 0;
    Set<Integer> vis = new HashSet<>();
    Deque<Integer> dup = new ArrayDeque<>();
    for (int i = 0; i < k; ++i) {
      int p = items[i][0], c = items[i][1];
      tot += p;
      if (!vis.add(c)) {
        dup.push(p);
      }
    }
    long ans = tot + (long)vis.size() * vis.size();
    for (int i = k; i < n; ++i) {
      int p = items[i][0], c = items[i][1];
      if (vis.contains(c) || dup.isEmpty()) {
        continue;
      }
      vis.add(c);
      tot += p - dup.pop();
      ans = Math.max(ans, tot + (long)vis.size() * vis.size());
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution { public: long long findMaximumElegance ( vector < vector < int >>& items , int k ) { sort ( items . begin (), items . end (), []( const vector < int >& a , const vector < int >& b ) { return a [ 0 ] > b [ 0 ]; }); long long tot = 0 ; unordered_set < int > vis ; stack < int > dup ; for ( int i = 0 ; i < k ; ++ i ) { int p = items [ i ][ 0 ], c = items [ i ][ 1 ]; tot += p ; if ( vis . count ( c )) { dup . push ( p ); } else { vis . insert ( c ); } } int n = items . size (); long long ans = tot + 1LL * vis . size () * vis . size (); for ( int i = k ; i < n ; ++ i ) { int p = items [ i ][ 0 ], c = items [ i ][ 1 ]; if ( vis . count ( c ) || dup . empty ()) { continue ; } vis . insert ( c ); tot += p - dup . top (); dup . pop (); ans = max ( ans , tot + ( long long ) ( 1LL * vis . size () * vis . size ())); } return ans ; } };
```

### Python

```python
class Solution : def findMaximumElegance ( self , items : List [ List [ int ]], k : int ) -> int : items . sort ( key = lambda x : - x [ 0 ]) tot = 0 vis = set () dup = [] for p , c in items [: k ]: tot += p if c not in vis : vis . add ( c ) else : dup . append ( p ) ans = tot + len ( vis ) ** 2 for p , c in items [ k :]: if c in vis or not dup : continue vis . add ( c ) tot += p - dup . pop () ans = max ( ans , tot + len ( vis ) ** 2 ) return ans
```