Greedy | Stack | No Heap or Priority Queue
Approach\nSort by profit from largest to smallest, and take the top k items. If there is already k different categories, we find the best possible profit. Other
# Approach\nSort by profit from largest to smallest, and take the top $$k$$ items. If there is already $$k$$ different categories, we find the best possible profit. Otherwise, we try to increase the number of categories and record each new total profit as we increase the catrgories.\n\nEvery time when we have a candidate item to swap with some existing item, we want to swap with the item that does not decrease the number of categories. In other words, we want to maintain a collection of items that are not the only item for their categories.\n\nWe don\'t have to use priority queue or heap. Because we have sorted the items beforehand. We only need to know whether this item is free to remove.\n\nFor each category, the first item within that category will never be swapped out. This is important property guaranteed by sorting beforehand.\n\n# Complexity\n- Time complexity:\n$$O(nlogn)$$\n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```\nclass Solution:\n    def findMaximumElegance(self, items: List[List[int]], k: int) -> int:\n        items.sort(reverse=True)\n        n = len(items)\n        # This stack contains all the items that we should feel\n        # free to discard when we want to have a new category.\n        stk = []\n        s = 0\n        # Whether this category has appeared before.\n        # When true, that means another item with higher profit\n        # and within the same category has been considered.\n        visited = [False] * (n + 1)\n        diff = 0\n        for i in range(k):\n            p, c = items[i]\n            s += p\n            # For each category, first visit == biggest profit\n            # within that caregory, and we never discard that item.\n            if visited[c]: stk.append(p)\n            else: diff += 1\n            visited[c] = True\n        if diff == k: return s + k * k\n        ans = s + diff * diff\n        i = k\n        while True:\n            # Find the next new category.\n            while i < n and visited[items[i][1]]:\n                i += 1\n            if i == n: break\n            p, c = items[i]\n            visited[c] = True\n            s += p - stk.pop()\n            diff += 1\n            ans = max(ans, s + diff * diff)\n            if diff == k: break\n        return ans\n```
['Array', 'Stack', 'Greedy', 'Python3']