Skip to main content

Heaps

Maximum Elegance of a K-Length Subsequence Solution In C++/Python/Java/JS

Problem Description

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

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.

Constraints

  • 1 <= items.length == n <= 10^5
  • items[i].length == 2
  • items[i][0] == profiti
  • items[i][1] == categoryi
  • 1 <= profiti <= 10^9
  • 1 <= categoryi <= n
  • 1 <= k <= n
💡
Try it Yourself First
We need to maximize the equation value while ensuring the x-coordinates satisfy a given constraint. Using a max-heap, we efficiently track valid points, removing those that exceed the allowed distance. This optimizes the search and ensures we find the maximum value efficiently.

Brute Force Approach

Intuition

The solution to this problem involves a greedy approach. The key observation is that higher profit items contribute more to the elegance score, but the number of distinct categories has a quadratic impact, making diversity just as important. Thus, we need to balance maximizing profit while also increasing the number of distinct categories where possible.

To do this, we first sort the items by profit in descending order and pick the top k items, ensuring the highest initial profit. However, this may include multiple items from the same category, limiting the quadratic benefit from distinct categories.

To handle this, we track duplicate categories separately. Once we have the first k items, we iterate through the remaining items. If an item introduces a new category, we check if we can swap it with a lower-profit duplicate from our selection. By doing this, we increase the distinct category count while keeping the total profit as high as possible.

At each step, we update and track the maximum elegance score achievable. This greedy approach efficiently balances high profits and category diversity, ensuring we get the best possible elegance within O(n log n) time.

Approach

Step 1: Sort Items by Profit

  • Sort the items array in descending order based on profit to prioritize selecting high-profit items first.

Step 2: Select Initial k Items

  • Pick the first k items greedily, assuming they provide the maximum total profit.
  • Maintain a visited array to track distinct categories.
  • Use a stack to store profits of duplicate-category items.

Step 3: Compute Initial Elegance

  • Calculate the initial elegance score using total_profit + distinct_categories².
  • If all k items have unique categories, return the result immediately.

Step 4: Try Replacing Duplicates with New Categories

  • Iterate through remaining items and check if they belong to a new category.
  • If a new category is found, replace the lowest-profit duplicate stored in the stack.
  • Update total_profit and increase the distinct category count.

Step 5: Track Maximum Elegance

  • Continuously update the maximum elegance score during replacements.

Step 6: Return the Maximum Elegance

  • After all possible replacements, return the highest elegance score obtained.

Dry Run

Input:

  • items = [[3,2], [5,1], [10,1]], k = 2

Step 1: Sort Items by Profit

  • Sort in descending order of profit:
  • items = [[10,1], [5,1], [3,2]]

Step 2: Select the First k Items

We pick the first k = 2 items:

Selected: [[10,1], [5,1]]

  • total_profit = 10 + 5 = 15
  • Categories: {1} (since both items have category 1)
  • Store duplicate category profit stk = [5]
  • distinct_categories = 1

Step 3: Compute Initial Elegance

  • Elegance formula: total_profit + distinct_categories²
  • 15 + (1 × 1) = 16

Step 4: Try Replacing Duplicates with New Categories

  • Next item: [3,2] (category 2 is new)
  • Replace stk.top() = 5 with 3
  • New total_profit = 15 - 5 + 3 = 13
  • distinct_categories = 2
  • Recompute elegance:
  • 13 + (2 × 2) = 17

Step 5: Return Maximum Elegance

Final max_elegance = 17

Code for All Languages
C++ 
// Approach: Stack-based Solution to Find Maximum Elegance
// Language: C++

class Solution {
public:
    long long findMaximumElegance(vector<vector<int>>& items, int k) {
        // Step 1: Sort items in descending order of profit.
        sort(items.begin(), items.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[0] > b[0];
        });

        int n = items.size();
        
        // Stack to store profits of duplicate category items.
        stack<int> stk;
        
        long long total_profit = 0;
        
        // Boolean vector to track visited categories.
        vector<bool> visited(n + 1, false);
        
        // Count of distinct categories in the selected k items.
        int distinct_categories = 0;

        // Step 2: Process the first k items.
        for (int i = 0; i < k; ++i) {
            int profit = items[i][0], category = items[i][1];
            total_profit += profit;

            // If category is already seen, push the profit to stack.
            if (visited[category]) {
                stk.push(profit);
            } else {
                distinct_categories++;
            }
            
            // Mark category as visited.
            visited[category] = true;
        }

        // Step 3: If all k items have unique categories, return the result immediately.
        if (distinct_categories == k) {
            return total_profit + 1LL * k * k;
        }

        // Initial elegance score.
        long long max_elegance = total_profit + 1LL * distinct_categories * distinct_categories;

        // Step 4: Try to replace duplicate category items with new categories.
        for (int i = k; i < n; ++i) {
            // Skip items with already visited categories.
            while (i < n && visited[items[i][1]]) {
                ++i;
            }

            // If there are no more new categories, break.
            if (i == n) break;

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

            // If we already have k distinct categories, stop.
            if (distinct_categories == k) break;

            // Mark the new category as visited.
            visited[category] = true;

            // Replace the lowest profit duplicate with the new category item.
            total_profit += profit - stk.top();
            stk.pop();

            // Increment the distinct categories count.
            distinct_categories++;

            // Update the max elegance score.
            max_elegance = max(max_elegance, total_profit + 1LL * distinct_categories * distinct_categories);
        }

        return max_elegance;
    }
};

Java 
// Approach: Stack-based Solution to Find Maximum Elegance
// Language: Java

import java.util.*;

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

        int n = items.length;

        // Stack to store profits of duplicate category items.
        Stack<Integer> stack = new Stack<>();

        long totalProfit = 0;

        // HashSet to track visited categories.
        Set<Integer> visited = new HashSet<>();

        // Count of distinct categories in the selected k items.
        int distinctCategories = 0;

        // Step 2: Process the first k items.
        for (int i = 0; i < k; i++) {
            int profit = items[i][0], category = items[i][1];
            totalProfit += profit;

            // If category is already seen, push the profit to the stack.
            if (visited.contains(category)) {
                stack.push(profit);
            } else {
                distinctCategories++;
            }

            // Mark category as visited.
            visited.add(category);
        }

        // Step 3: If all k items have unique categories, return the result immediately.
        if (distinctCategories == k) {
            return totalProfit + (long) k * k;
        }

        // Initial elegance score.
        long maxElegance = totalProfit + (long) distinctCategories * distinctCategories;

        // Step 4: Try to replace duplicate category items with new categories.
        for (int i = k; i < n; i++) {
            // Skip items with already visited categories.
            while (i < n && visited.contains(items[i][1])) {
                i++;
            }

            // If there are no more new categories, break.
            if (i == n) break;

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

            // If we already have k distinct categories, stop.
            if (distinctCategories == k) break;

            // Mark the new category as visited.
            visited.add(category);

            // Replace the lowest profit duplicate with the new category item.
            totalProfit += profit - stack.pop();

            // Increment the distinct categories count.
            distinctCategories++;

            // Update the max elegance score.
            maxElegance = Math.max(maxElegance, totalProfit + (long) distinctCategories * distinctCategories);
        }

        return maxElegance;
    }
}

Python 
# Approach: Stack-based Solution to Find Maximum Elegance
# Language: Python

class Solution(object):
    def findMaximumElegance(self, items, k):
        """
        :type items: List[List[int]]
        :type k: int
        :rtype: int
        """

        # Step 1: Sort items in descending order of profit.
        items.sort(key=lambda x: -x[0])

        n = len(items)

        # Stack to store profits of duplicate category items.
        stack = []

        total_profit = 0

        # Set to track visited categories.
        visited = set()

        # Count of distinct categories in the selected k items.
        distinct_categories = 0

        # Step 2: Process the first k items.
        for i in range(k):
            profit, category = items[i]
            total_profit += profit

            # If category is already seen, push the profit to the stack.
            if category in visited:
                stack.append(profit)
            else:
                distinct_categories += 1

            # Mark category as visited.
            visited.add(category)

        # Step 3: If all k items have unique categories, return the result immediately.
        if distinct_categories == k:
            return total_profit + k * k

        # Initial elegance score.
        max_elegance = total_profit + distinct_categories * distinct_categories

        # Step 4: Try to replace duplicate category items with new categories.
        i = k
        while i < n:
            # Skip items with already visited categories.
            while i < n and items[i][1] in visited:
                i += 1

            # If there are no more new categories, break.
            if i == n:
                break

            profit, category = items[i]

            # If we already have k distinct categories, stop.
            if distinct_categories == k:
                break

            # Mark the new category as visited.
            visited.add(category)

            # Replace the lowest profit duplicate with the new category item.
            total_profit += profit - stack.pop()

            # Increment the distinct categories count.
            distinct_categories += 1

            # Update the max elegance score.
            max_elegance = max(max_elegance, total_profit + distinct_categories * distinct_categories)

            i += 1

        return max_elegance

Javascript 
/**
 * Approach: Stack-based Solution to Find Maximum Elegance
 * Language: JavaScript
 * 
 * @param {number[][]} items - Array of items where each item contains [profit, category].
 * @param {number} k - Number of items to select.
 * @return {number} - Maximum elegance score.
 */
var findMaximumElegance = function(items, k) {
    // Step 1: Sort items in descending order of profit.
    items.sort((a, b) => b[0] - a[0]);

    let n = items.length;

    // Stack to store profits of duplicate category items.
    let stack = [];

    let totalProfit = 0;

    // Set to track visited categories.
    let visited = new Set();

    // Count of distinct categories in the selected k items.
    let distinctCategories = 0;

    // Step 2: Process the first k items.
    for (let i = 0; i < k; i++) {
        let [profit, category] = items[i];
        totalProfit += profit;

        // If category is already seen, push the profit to stack.
        if (visited.has(category)) {
            stack.push(profit);
        } else {
            distinctCategories++;
        }

        // Mark category as visited.
        visited.add(category);
    }

    // Step 3: If all k items have unique categories, return the result immediately.
    if (distinctCategories === k) {
        return totalProfit + k * k;
    }

    // Initial elegance score.
    let maxElegance = totalProfit + distinctCategories * distinctCategories;

    // Step 4: Try to replace duplicate category items with new categories.
    let i = k;
    while (i < n) {
        // Skip items with already visited categories.
        while (i < n && visited.has(items[i][1])) {
            i++;
        }

        // If there are no more new categories, break.
        if (i === n) break;

        let [profit, category] = items[i];

        // If we already have k distinct categories, stop.
        if (distinctCategories === k) break;

        // Mark the new category as visited.
        visited.add(category);

        // Replace the lowest profit duplicate with the new category item.
        totalProfit += profit - stack.pop();

        // Increment the distinct categories count.
        distinctCategories++;

        // Update the max elegance score.
        maxElegance = Math.max(maxElegance, totalProfit + distinctCategories * distinctCategories);

        i++;
    }

    return maxElegance;
};

Time Complexity Analysis: O(n log n)

Let n be the number of items in the input array.

Sorting Step:

  • We sort the items in descending order of profit, which takes O(n log n) time.

Processing the First k Items:

  • We iterate through the first k items, maintaining total profit and tracking distinct categories. This takes O(k) ≈ O(n) in the worst case.

Replacing Duplicates with New Categories:

  • We iterate over the remaining n - k items to check for new categories. In the worst case, we perform up to O(n) operations.

Stack Operations:

  • Each duplicate category profit is pushed onto a stack and later popped at most k times, contributing O(k) ≈ O(n) in the worst case.

Final Time Complexity: O(n log n)

Space Complexity Analysis: O(n)

Auxiliary Space Complexity: O(n)

  • We maintain a visited array of size n + 1 to track distinct categories, contributing O(n) space.
  • We also use a stack to store profits of duplicate category items, which can store at most k elements. Since k ≤ n, this contributes O(n) space in the worst case.
  • Other variables such as total_profit and distinct_categories use only O(1) space.

Total Auxiliary Space Complexity: O(n)

Total Space Complexity: O(n)

  • The input array items takes O(n) space.
  • The extra space used by the algorithm is also O(n) (from the visited array and stack).

Final Space Complexity:O(n) + O(n) = O(n).

The brute-force approach checks all pairs, which is inefficient. Using a max-heap, we track valid points dynamically, removing those that exceed the distance constraint. This ensures we efficiently find the maximum value while reducing unnecessary computations.

Optimal Approach

Intuition

The brute-force approach for this problem involves sorting the items based on profit and then using a stack to track duplicate categories while iterating through the first k elements. While this approach ensures that we consider only the highest-profit items first, the replacement process is inefficient. When trying to maximize elegance, it relies on a linear search through the sorted array to find a new category, which can result in unnecessary traversals. Since replacing duplicate categories is handled using a stack, the worst case could lead to unnecessary iterations, making it suboptimal.

To optimize this, a Min-Heap (Priority Queue) can be used instead of a stack. The core idea behind the optimal solution is that rather than manually tracking duplicate category items using a stack and performing linear lookups, we use a heap to efficiently identify the least valuable duplicate to replace. The heap is structured in such a way that the smallest profit duplicate is always at the top, ensuring that we can replace it with a new category item in O(logk) time instead of an unpredictable number of linear iterations.

By leveraging a hash map to track category frequencies and a min-heap to manage duplicate category profits, the process of replacing duplicate items becomes more systematic. When encountering an item with a new category, the heap allows for a quick lookup of the lowest-profit duplicate, and its removal is guaranteed to be efficient. This structured replacement reduces the time complexity from O(n) worst-case searches to O(logk) per replacement operation.

Overall, the brute-force stack-based approach runs in
O(nlogn) due to sorting and inefficient duplicate replacement, while the optimized heap-based approach achieves the same sorting complexity but improves replacement operations using a heap, maintaining an overall complexity of O(nlogn) while ensuring better efficiency in handling replacements.

Approach

Step 1: Sort Items by Profit

  • Sort the given items in descending order of profit.
  • This ensures that we always consider the most profitable items first when selecting the top k items.

Step 2: Initialize a Hash Map and Min-Heap

  • Use an unordered_map to track the count of items in each category.
  • Use a Min-Heap (Priority Queue) to store duplicate category items, maintaining a structure where the smallest profit duplicate is always at the top.

Step 3: Process the First k Items

  • Iterate through the first k items and:
  • Add the profit to the total profit sum.
  • Update the category count in the hash map.
  • Push duplicate category items into the Min-Heap (sorted by profit).
  • Compute the initial elegance score as:
  • elegance=total profit+(distinct categories)^2

Step 4: Replace Duplicate Items with New Categories

  • Iterate through the remaining items beyond index k.
  • If the item's category already exists in the selection, skip it.
  • Otherwise:
  • Extract the smallest profit duplicate from the Min-Heap.
  • Ensure that we do not remove a unique category (only remove duplicates).
  • Replace the duplicate item with the new category item, updating the total profit and the category count.
  • Recalculate the elegance score and update the maximum found so far.

Step 5: Return the Maximum Elegance Score

  • After processing all items, return the highest elegance score computed during the iterations.

Dry Run

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

Expected Output: 17

Step 1: Sort Items by Profit

  • Sorting in descending order of profit:
  • Sorted Items = [(10,1), (5,1), (3,2)]

Step 2: Process the First k = 2 Items

Pick (10,1):

  • Total Profit = 10
  • Distinct Categories = {1}
  • Heap (for duplicates) = []

Pick (5,1):

  • Total Profit = 10 + 5 = 15
  • Distinct Categories = {1} (Category already present)
  • Heap stores duplicate: [5]

Initial Elegance Calculation:

  • Elegance = Total Profit + (Number of Distinct Categories)^2
  • Elegance = 15 + (1 × 1) = 16

Step 3: Try Replacing a Duplicate with a New Category

  • Next item (3,2) belongs to a new category (2).
  • Since we have a duplicate (5 from category 1), replace it with (3,2).

Profit Update:

  • Remove 5, add 3:
  • New Total Profit = 15 - 5 + 3 = 13

Update Distinct Categories:

  • Now have {1, 2} (2 distinct categories)

New Elegance Calculation:

  • Elegance = 13 + (2 × 2) = 17

Update Maximum Elegance:

  • Maximum Elegance = max(16, 17) = 17

Final Output: 17

Code for All Languages
C++ 
// Approach: Heap-Based Solution to Find Maximum Elegance
// Language: C++

class Solution {
public:
    long long findMaximumElegance(vector<vector<int>>& items, int k) 
    {
        // Step 1: Sort items in descending order of profit.
        sort(items.begin(), items.end(), greater<vector<int>>());

        // Step 2: Use a hash map to track category frequencies.
        unordered_map<int, int> category_count;
        
        // Min-heap to store duplicate category items based on profit.
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

        long long total_profit = 0;
        long long max_elegance = 0;

        // Step 3: Process the first k items.
        for (int i = 0; i < k; i++) 
        {
            // Add profit.
            total_profit += items[i][0];

            // Count category occurrences.
            category_count[items[i][1]]++;

            // Store item in heap.
            pq.push({items[i][0], items[i][1]});
        }

        // Calculate initial elegance.
        max_elegance = total_profit + 1LL * category_count.size() * category_count.size();

        int n = items.size();

        // Step 4: Try to replace duplicate category items with new categories.
        for (int i = k; i < n && !pq.empty(); i++) 
        {
            // If category is already included, continue.
            if (category_count.count(items[i][1])) 
                continue;

            // Find a category with multiple instances to replace.
            auto it = pq.top();
            pq.pop();
            
            // Ensure we don't remove a unique category.
            while (!pq.empty() && category_count[it.second] == 1) 
            {
                it = pq.top();
                pq.pop();
            }

            // If heap is empty, no replacement is possible.
            if (pq.empty()) 
                break;

            // Replace a duplicate item with a new category.
            total_profit += items[i][0] - it.first;
            category_count[it.second]--;
            category_count[items[i][1]]++;

            // Update max elegance score.
            long long new_elegance = total_profit + 1LL * category_count.size() * category_count.size();
            max_elegance = max(max_elegance, new_elegance);
        }

        return max_elegance;
    }
};

Java 
// Approach: Heap-Based Solution to Find Maximum Elegance
// Language: Java

import java.util.*;

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

        // Step 2: Use a hash map to track category frequencies.
        Map<Integer, Integer> categoryCount = new HashMap<>();

        // Min-heap to store duplicate category items based on profit.
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));

        long totalProfit = 0;
        long maxElegance = 0;

        // Step 3: Process the first k items.
        for (int i = 0; i < k; i++) {
            // Add profit.
            totalProfit += items[i][0];

            // Count category occurrences.
            categoryCount.put(items[i][1], categoryCount.getOrDefault(items[i][1], 0) + 1);

            // Store item in heap.
            minHeap.offer(new int[]{items[i][0], items[i][1]});
        }

        // Calculate initial elegance.
        maxElegance = totalProfit + (long) categoryCount.size() * categoryCount.size();

        int n = items.length;

        // Step 4: Try to replace duplicate category items with new categories.
        for (int i = k; i < n && !minHeap.isEmpty(); i++) {
            // If category is already included, continue.
            if (categoryCount.containsKey(items[i][1])) 
                continue;

            // Find a category with multiple instances to replace.
            int[] top = minHeap.poll();

            // Ensure we don't remove a unique category.
            while (!minHeap.isEmpty() && categoryCount.get(top[1]) == 1) {
                top = minHeap.poll();
            }

            // If heap is empty, no replacement is possible.
            if (minHeap.isEmpty()) 
                break;

            // Replace a duplicate item with a new category.
            totalProfit += items[i][0] - top[0];
            categoryCount.put(top[1], categoryCount.get(top[1]) - 1);
            categoryCount.put(items[i][1], categoryCount.getOrDefault(items[i][1], 0) + 1);

            // Update max elegance score.
            long newElegance = totalProfit + (long) categoryCount.size() * categoryCount.size();
            maxElegance = Math.max(maxElegance, newElegance);
        }

        return maxElegance;
    }
}

Python 
# Approach: Heap-Based Solution to Find Maximum Elegance
# Language: Python

import heapq

class Solution:
    def findMaximumElegance(self, items, k):
        """
        :type items: List[List[int]]
        :type k: int
        :rtype: int
        """
        # Step 1: Sort items in descending order of profit.
        items.sort(reverse=True, key=lambda x: x[0])
        
        # Step 2: Use a dictionary to track category frequencies.
        category_count = {}
        
        # Min-heap to store duplicate category items based on profit.
        min_heap = []
        
        total_profit = 0
        max_elegance = 0

        # Step 3: Process the first k items.
        for i in range(k):
            # Add profit.
            total_profit += items[i][0]

            # Count category occurrences.
            category_count[items[i][1]] = category_count.get(items[i][1], 0) + 1

            # Store item in heap.
            heapq.heappush(min_heap, (items[i][0], items[i][1]))

        # Calculate initial elegance.
        max_elegance = total_profit + len(category_count) ** 2

        n = len(items)

        # Step 4: Try to replace duplicate category items with new categories.
        for i in range(k, n):
            # If category is already included, continue.
            if items[i][1] in category_count:
                continue

            # Find a category with multiple instances to replace.
            while min_heap and category_count[min_heap[0][1]] == 1:
                heapq.heappop(min_heap)

            # If heap is empty, no replacement is possible.
            if not min_heap:
                break

            # Remove the least profitable duplicate item.
            least_profit, least_category = heapq.heappop(min_heap)
            total_profit += items[i][0] - least_profit

            # Update category counts.
            category_count[least_category] -= 1
            if category_count[least_category] == 0:
                del category_count[least_category]

            category_count[items[i][1]] = category_count.get(items[i][1], 0) + 1

            # Update max elegance score.
            new_elegance = total_profit + len(category_count) ** 2
            max_elegance = max(max_elegance, new_elegance)

        return max_elegance

Javascript 
// Approach: Heap-Based Solution to Find Maximum Elegance
// Language: JavaScript

/**
 * @param {number[][]} items
 * @param {number} k
 * @return {number}
 */
var findMaximumElegance = function(items, k) {
    // Step 1: Sort items in descending order of profit.
    items.sort((a, b) => b[0] - a[0]);

    // Step 2: Use a Map to track category frequencies.
    let categoryCount = new Map();
    
    // Min-heap to store duplicate category items based on profit.
    let minHeap = new MinHeap();

    let totalProfit = 0;
    let maxElegance = 0;

    // Step 3: Process the first k items.
    for (let i = 0; i < k; i++) {
        // Add profit.
        totalProfit += items[i][0];

        // Count category occurrences.
        categoryCount.set(items[i][1], (categoryCount.get(items[i][1]) || 0) + 1);

        // Store item in heap.
        minHeap.push([items[i][0], items[i][1]]);
    }

    // Calculate initial elegance.
    maxElegance = totalProfit + categoryCount.size ** 2;

    let n = items.length;

    // Step 4: Try to replace duplicate category items with new categories.
    for (let i = k; i < n; i++) {
        // If category is already included, continue.
        if (categoryCount.has(items[i][1])) continue;

        // Find a category with multiple instances to replace.
        while (!minHeap.isEmpty() && categoryCount.get(minHeap.peek()[1]) === 1) {
            minHeap.pop();
        }

        // If heap is empty, no replacement is possible.
        if (minHeap.isEmpty()) break;

        // Remove the least profitable duplicate item.
        let [leastProfit, leastCategory] = minHeap.pop();
        totalProfit += items[i][0] - leastProfit;

        // Update category counts.
        categoryCount.set(leastCategory, categoryCount.get(leastCategory) - 1);
        if (categoryCount.get(leastCategory) === 0) {
            categoryCount.delete(leastCategory);
        }

        categoryCount.set(items[i][1], (categoryCount.get(items[i][1]) || 0) + 1);

        // Update max elegance score.
        let newElegance = totalProfit + categoryCount.size ** 2;
        maxElegance = Math.max(maxElegance, newElegance);
    }

    return maxElegance;
};

// MinHeap implementation for JavaScript
class MinHeap {
    constructor() {
        this.heap = [];
    }

    push(val) {
        this.heap.push(val);
        this._heapifyUp();
    }

    pop() {
        if (this.heap.length === 1) return this.heap.pop();
        let min = this.heap[0];
        this.heap[0] = this.heap.pop();
        this._heapifyDown();
        return min;
    }

    peek() {
        return this.heap[0];
    }

    isEmpty() {
        return this.heap.length === 0;
    }

    _heapifyUp() {
        let index = this.heap.length - 1;
        while (index > 0) {
            let parentIndex = Math.floor((index - 1) / 2);
            if (this.heap[index][0] >= this.heap[parentIndex][0]) break;
            [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
            index = parentIndex;
        }
    }

    _heapifyDown() {
        let index = 0;
        while (2 * index + 1 < this.heap.length) {
            let smallest = 2 * index + 1;
            let right = 2 * index + 2;
            if (right < this.heap.length && this.heap[right][0] < this.heap[smallest][0]) {
                smallest = right;
            }
            if (this.heap[index][0] <= this.heap[smallest][0]) break;
            [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
            index = smallest;
        }
    }
}

Time Complexity Analysis: O(n log n)

Let n be the number of items in the input array and k be the subsequence size constraint.

Sorting the Items: O(n log n)

  • The first step sorts the items based on profit in descending order.
  • Sorting an array of size n takes O(n log n).

Processing the First k Items: O(k log k)

  • We insert k items into a min-heap, where each insertion takes O(log k).
  • This results in a total time complexity of O(k log k).

Iterating Over Remaining Items: O(n log k)

  • We iterate over the remaining (n - k) items.
  • For each item, we may replace an element in the heap, which involves:
  • Popping an element: O(log k)
  • Inserting a new element: O(log k)
  • Since this happens for at most (n - k) items, the time complexity is O((n - k) log k) = O(n log k).

Overall Complexity: O(n log n)

  • Sorting: O(n log n)
  • Heap operations: O(k log k) + O(n log k) = O(n log k)
  • Since k ≤ n, in the worst case log k ≈ log n, so O(n log k) ≈ O(n log n).
  • Final complexity: O(n log n)

Thus, the overall time complexity of the algorithm is O(n log n).

Space Complexity Analysis: O(n)

Sorting Storage: O(n)

  • Sorting the items array happens in-place, meaning no extra space is needed.
  • However, if sorting is not in-place, it requires O(n) space.

Hash Map for Category Count: O(n)

  • The unordered_map category_count stores the frequency of each category.
  • In the worst case, all n items have unique categories, leading to O(n) space.

Min-Heap for Duplicate Tracking: O(k) ⊆ O(n)

  • The priority queue (min-heap) stores at most k elements (the subsequence size).
  • In the worst case, k = n, so it takes O(n) space.

Auxiliary Space (O(1))

  • A few integer/long long variables are used (total_profit, max_elegance), taking O(1) space.

Final Space Complexity:O(n)

  • The dominant space usage comes from the hash map (O(n)) and min-heap (O(k) ⊆ O(n)).
  • Thus, the overall space complexity remains O(n).

Similar Problems

Now we have successfully tackled this problem, let’s try these similar problems.

Kth Largest Element in an Array

Given an integer array nums and an integer k, return the kth largest element in the array.Note that it is the kth largest element in the sorted order, not the kth distinct element.

Find Median from Data Stream

This problem requires continuously finding the median of a growing data stream. It uses two heaps (a max-heap for the left half and a min-heap for the right half) to efficiently balance and retrieve the median in O(log n) insertion and O(1) retrieval time, similar to how we maintain the k-th largest element in a min-heap.