Python - WITH & WITHOUT A HEAP ✅
The elegance of a subsequence is given as - \n\n\ttotal_profit + distinct_categories^2\n\t\nThis means, for the maximum elegance, we need to maximize not just t
The elegance of a subsequence is given as - \n\n\ttotal_profit + distinct_categories^2\n\t\nThis means, for the maximum elegance, we need to maximize not just the profit, but also the distinct categories. Ofcourse it is not always possible that both are maximized at the same time so we want to balance them such that the elegance value we get is the maximum.\n\nWhen we have such problems, we can try to maximize one part first, and then try to work on the other part. Here, we will do the same. We can try to maximize the total_profit first. And that is pretty simple. We just need to sort the items by their "profit" values in decreasing order, and then pick the first "k" items for our subsequence. That will be the "k" length subsequence with highest "total_profit".\n\nNow that our profit is maximized, we want to increase the "distinct_categories" in our subsequence. \n\nLet\'s take an example to understand how that will be done.\n\n\tSuppose, we have items = [[3,2],[5,1],[10,1]], k = 2\n\t\n\tWhen we sort items in decreasing order of their profit, we get - \n\t\n\t\titems = [[10,1], [5,1], [3,2]]\n\t\t\n\tSo, the "k" length subsequence with highest total_profit is [[10,1],[5,1]]\n\t\n\tAnd for this, elegance is (10+5) * 1 => 16\n\t\n\tNow, how can we increase this elegance further?\n\t\n\tWe have already maximized "total_profit".\n\t\n\tSo, the other term we can play around with is "distinct_categories"\n\t\n\tCurrently, the distinct_categories is "1"\n\t\n\tBut, what if, we can remove one item and replace it with an item with a different category?\n\t\n\tThat will increase the distinct_categories count to "2"\n\t\n\tWe have [3,2] and we can replace either [10,1] or [5,1]\n\t\n\tWe can replace some item because [3,2] has a category "2" \n\twhich is not already present in the current subsequence.\n\t\n\tIt means, addin this item will increase the distinct_categories.\n\t\n\tNow, which one to replace among [10,1] and [5,1]?\n\t\n\tOfcourse it is the one that has a lower profit value because remember that,\n\twe want to balance "total_profit" and "distinct_categories"\n\t\n\tSo, we replace and the new subsequence we get is [[10,1],[3,2]]\n\tThe new elegance is (10 + 3) + (2*2) => 17\n\t\n\tAnd this is higher than previous elegance value.\n\t\n\tSo, the maximum elegance possible is "17".\n\t\nAnd this is the idea.\n\n# **1. USING A MIN HEAP**\n\nWe first get the "k" length subsequence with the highest total_profit value. When we create that subsequence, if current item has a category that is already present in the subsequence, we also add that item to a minHeap which keeps all the candidates which can be replaced by other items in the range [k,n-1]. This minHeap will order them by their profit values from smallest to largest. So at any time, the item we will replace will always be the one having the smallest profit.\n\nAs we saw in above example, we could replace an item with [3,2] only because the category "2" is not already present in the subsequence. And that\'s the logic we also use in the code. We only do this replacement if the current item\'s category is not already present. And to keep track of this, we can use a Set. If current item\'s category is not present already, it means adding this new item will increase the distincts_count value and might also increase the elegance (not always the case).\n\nSo, we will update the elegance accordingly.\n\n\n```\ndef findMaximumElegance(self, items: List[List[int]], k: int) -> int:\n        \n        # Length of the list\n        n = len(items)\n        \n        # Sort the items by profit in decreasing order\n        items.sort(reverse=True)\n        \n        # Get the first "k" items for the first subsequence\n        # This will ensure that we have the "k" items with maximum profit\n        # Also, to keep track of each category we can use a set\n        # This will help us to check if a category is already present in current subsequence or not\n        categories = set()\n        \n        # Total profit\n        totalProfit = 0\n        \n        # A Min Heap to keep track of the items based on their profits from smallest to largest\n        # This Min Heap will contain those items whose category occurs more than once in the "k" length subsequence\n        # Since our motive is to also maximize distinct categories\n        minHeap = []\n        \n        for i in range(k):\n            \n            # Update the profit so far\n            totalProfit += items[i][0]\n            \n            # if this category already exists in the subsequence so far\n            if items[i][1] in categories:\n                \n                # Put the item into the minHeap\n                heappush(minHeap, items[i][0])\n            \n            # Add to the set\n            categories.add(items[i][1])\n            \n        # Maximum Elegance\n        # Initialize it with the current elegance\n        maxElegance = totalProfit + (len(categories) ** 2)\n        \n        # Now, we go over the rest of the values\n        for i in range(k,n):\n            \n            # If the minheap is empty, there is no item left to replace, so we can return the maxElegance here\n            if not minHeap: return maxElegance\n            \n            # If current item has a category that is not already present in the current subsequence\n            # Then, we can replace the item on top of the minHeap with this item\n            # Since we have sorted the list by the profit initially\n            # It also means current item is the item with highest profit among all items of its category\n            if items[i][1] not in categories:\n                \n                # We can replace the item on top of minHeap with current item\n                # Hence, pop the top of the minHeap\n                top = heappop(minHeap)\n    \n                # If current item is added to the subsequence, what will be the new total profit\n                newTotalProfit = totalProfit - top + items[i][0]\n                \n                # The count of distincts will increase by 1\n                newDistinctCount = len(categories) + 1\n                \n                # So, what will be the new elegance\n                newElegance = newTotalProfit + (newDistinctCount ** 2)\n                \n                # Add the current category to the set\n                categories.add(items[i][1])\n                \n                # Update the total profit\n                totalProfit = newTotalProfit\n\n                # If new elegance is higher than maxElegance so far\n                maxElegance = max(maxElegance, newElegance)\n        \n        # Return the maximum elegance\n        return maxElegance\n```\n\n# **2. WITHOUT USING A MIN HEAP**\nSince we have already sorted the items by profit in decreasing order, it means, when we get the candidates that can be replaced, they will also be in a sorted order based on their profit values from highest to lowest. So, there is no need to use a Heap. Instead, we can use a simple list and at any time, the item that we should replace will always be at the end of this list.\n\n```\ndef findMaximumElegance(self, items: List[List[int]], k: int) -> int:\n        \n        # Length of the list\n        n = len(items)\n        \n        # Sort the items by profit in decreasing order\n        items.sort(reverse=True)\n        \n        # Get the first "k" items for the first subsequence\n        # This will ensure that we have the "k" items with maximum profit\n        # Also, to keep track of each category we can use a set\n        # This will help us to check if a category is already present in current subsequence or not\n        categories = set()\n        \n        # Total profit\n        totalProfit = 0\n        \n        # A simple list track of the items based on their profits from smallest to largest\n        # There is no need to use a Heap because since the list is sorted based on profits already\n        # The candidate list will also be sorted in decreasing order\n        # So at any time, the best item to replace will be at the end of the list\n        candidates = []\n        \n        for i in range(k):\n            \n            # Update the profit so far\n            totalProfit += items[i][0]\n            \n            # if this category already exists in the subsequence so far\n            if items[i][1] in categories:\n                \n                # Put the item into the candidates list\n                candidates.append(items[i][0])\n            \n            # Add to the set\n            categories.add(items[i][1])\n            \n        # Maximum Elegance\n        # Initialize it with the current elegance\n        maxElegance = totalProfit + (len(categories) ** 2)\n        \n        # Now, we go over the rest of the values\n        for i in range(k,n):\n            \n            # If the candidates list is empty, there is no item left to replace, so we can return the maxElegance here\n            if not candidates: return maxElegance\n            \n            # If current item has a category that is not already present in the current subsequence\n            # Then, we can replace the item at the end of candidates list with this item\n            # Since we have sorted the list by the profit initially\n            # It also means current item is the item with highest profit among all items of its category\n            if items[i][1] not in categories:\n                \n                # We can replace the item\n                # Hence, pop the item at the end of candidates list\n                top = candidates.pop()\n    \n                # If current item is added to the subsequence, what will be the new total profit\n                newTotalProfit = totalProfit - top + items[i][0]\n                \n                # The count of distincts will increase by 1\n                newDistinctCount = len(categories) + 1\n                \n                # So, what will be the new elegance\n                newElegance = newTotalProfit + (newDistinctCount ** 2)\n                \n                # Add the current category to the set\n                categories.add(items[i][1])\n                \n                # Update the total profit\n                totalProfit = newTotalProfit\n\n                # If new elegance is higher than maxElegance so far\n                maxElegance = max(maxElegance, newElegance)\n        \n        # Return the maximum elegance\n        return maxElegance\n```
['Sorting', 'Heap (Priority Queue)', 'Ordered Set', 'Python']