Maximum Elegance of a K-Length Subsequence

Maximum Elegance of a K-Length Subsequence - Problem

Array Hash Table Stack Greedy Sorting Heap (Priority Queue) Hard

You are given a 0-indexed 2D integer array items of length n and an integer k.

items[i] = [profit_i, category_i], where profit_i and category_i denote the profit and category of the i^th item respectively.

Let's define the elegance of a subsequence of items as total_profit + distinct_categories², 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.

Input & Output

Example 1 — Basic Case

$ Input: items = [[3,2],[5,1],[10,1]], k = 2

› Output: 17

💡 Note: Select items [5,1] and [10,1]: total_profit = 15, distinct_categories = 1, elegance = 15 + 1² = 16. Alternative: [3,2] and [10,1]: total_profit = 13, distinct_categories = 2, elegance = 13 + 2² = 17 (optimal).

Example 2 — Higher Diversity Bonus

$ Input: items = [[3,1],[3,1],[5,2],[6,3]], k = 3

› Output: 19

💡 Note: Select [3,1], [5,2], [6,3]: total_profit = 14, distinct_categories = 3, elegance = 14 + 3² = 23. But we can only select 3 items, best is [3,1], [5,2], [6,3] = 14 + 9 = 23. Actually, optimal is [6,3], [5,2], [3,1] giving 14 + 9 = 23, but wait - this has 3 categories. Let me recalculate: we get profit 14 with 3 distinct categories, so 14 + 3² = 23. But the expected is 19, so the optimal might be different selection.

Example 3 — All Same Category

$ Input: items = [[1,1],[2,1],[3,1]], k = 2

› Output: 6

💡 Note: All items have the same category. Best selection is [2,1] and [3,1]: total_profit = 5, distinct_categories = 1, elegance = 5 + 1² = 6.

Constraints

1 ≤ items.length ≤ 10⁵
items[i].length == 2
1 ≤ items[i][0], items[i][1] ≤ 10⁹
1 ≤ k ≤ items.length

Visualization

Tap to expand

Understanding the Visualization

Input Items

Each item has [profit, category]

Calculate Elegance

Elegance = total_profit + distinct_categories²

Find Maximum

Select k items to maximize elegance

Key Takeaway

🎯 Key Insight: The squared category bonus means diversity can be more valuable than pure profit maximization

Asked in

G Google 15 f Meta 12 a Amazon 8

The key insight is balancing profit with category diversity since the diversity bonus is squared. The greedy approach sorts by profit and uses stack-based optimization to replace duplicates with new categories. Time: O(n log n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Greedy with Stack Optimization	O(n log n)	O(n)	Sort by profit, select top k items, then optimize by swapping duplicates for new categories
Brute Force - Try All Combinations	O(C(n,k) × k)	O(k)	Generate all possible k-length subsequences and calculate elegance for each

Greedy with Stack Optimization — Algorithm Steps

Sort items by profit in descending order
Take top k items as initial selection
Use a stack to track duplicate category items
Try swapping duplicates with items from unused categories
Calculate elegance for each valid configuration

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort by Profit

Arrange items by profit in descending order

Select Top K

Take k highest profit items, track duplicates in stack

Optimize Categories

Replace duplicates with new categories when beneficial

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int compare(const void* a, const void* b) {
    int* item1 = *(int**)a;
    int* item2 = *(int**)b;
    return item2[0] - item1[0];  // Descending order by profit
}

long long solution(int items[][2], int n, int k) {
    // Create array of pointers for sorting
    int** itemPtrs = (int**)malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++) {
        itemPtrs[i] = items[i];
    }
    
    // Sort by profit descending
    qsort(itemPtrs, n, sizeof(int*), compare);
    
    long long totalProfit = 0;
    bool categories[1001] = {false};  // Assuming categories are reasonable
    int stack[1000];  // Stack for duplicate profits
    int stackSize = 0;
    int distinctCount = 0;
    
    // Take the first k items (highest profits)
    for (int i = 0; i < k; i++) {
        int profit = itemPtrs[i][0];
        int category = itemPtrs[i][1];
        totalProfit += profit;
        if (categories[category]) {
            stack[stackSize++] = profit;  // Store duplicate profit
        } else {
            categories[category] = true;
            distinctCount++;
        }
    }
    
    long long maxElegance = totalProfit + (long long)distinctCount * distinctCount;
    
    // Try to replace duplicates with new categories
    for (int i = k; i < n; i++) {
        if (stackSize == 0) break;  // No more duplicates
        
        int profit = itemPtrs[i][0];
        int category = itemPtrs[i][1];
        if (!categories[category]) {
            // Remove the last duplicate profit
            int removedProfit = stack[--stackSize];
            totalProfit = totalProfit - removedProfit + profit;
            categories[category] = true;
            distinctCount++;
            
            long long elegance = totalProfit + (long long)distinctCount * distinctCount;
            if (elegance > maxElegance) {
                maxElegance = elegance;
            }
        }
    }
    
    free(itemPtrs);
    return maxElegance;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for 2D array
    int items[100][2];
    int n = 0;
    
    char* ptr = line + 1; // Skip first '['
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            items[n][0] = strtol(ptr, &ptr, 10);
            ptr++; // Skip comma
            items[n][1] = strtol(ptr, &ptr, 10);
            n++;
            while (*ptr && *ptr != ']') ptr++;
            if (*ptr) ptr++;
        } else {
            ptr++;
        }
    }
    
    int k;
    scanf("%d", &k);
    
    printf("%lld\n", solution(items, n, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting dominates the time complexity

⚡ Linearithmic

Space Complexity

O(n)

Space for sorted array, sets for categories, and stack for duplicates

⚡ Linearithmic Space

15.2K Views

Medium Frequency

~35 min Avg. Time

423 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy with Stack Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler