Python 3   || head vs tail   ||   T/S: 99% / 31%
\nclass Solution:\n    def findMaximumElegance(self, items: List[List[int]], k: int) -> int:\n\n        items.sort(reverse = True)\n        sm, seenCats, dups =
```\nclass Solution:\n    def findMaximumElegance(self, items: List[List[int]], k: int) -> int:\n\n        items.sort(reverse = True)\n        sm, seenCats, dups = 0, set(), deque()\n\n        for headPrf, headCat in items[:k]:\n            \n            sm+= headPrf\n\n            if headCat in seenCats: dups.append(headPrf)\n            else: seenCats.add(headCat)\n\n        numCats = len(seenCats)    \n\n        ans = sm = sm + numCats*numCats\n        \n        for tailPrf, tailCat in items[k:]:\n\n            if not dups or tailCat in seenCats: continue\n            numCats+= 1\n            diff = tailPrf - dups.pop() + 2 * numCats - 1\n                                       # a**2 - (a-1)**2 -  = 2*a - 1\n            sm += diff  \n            if diff > 0: ans = sm\n            seenCats.add(tailCat)\n\n        return ans\n```\n[https://leetcode.com/problems/maximum-elegance-of-a-k-length-subsequence/submissions/1295907224/](https://leetcode.com/problems/maximum-elegance-of-a-k-length-subsequence/submissions/1295907224/)\n\n\nI could be wrong, but I think that time complexity is *O*(*N* log *N*) and space complexity is *O*(*N*), in which *N* ~ `len(items)`.
['Python3']