Easy and Intuitive Python soln🔥
Intuition\n Describe your first thoughts on how to solve this problem. \ngreedy\n# Approach\n Describe your approach to solving the problem. \nsort w.r.t profit
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\ngreedy\n# Approach\n<!-- Describe your approach to solving the problem. -->\nsort w.r.t profit from higher to lower. Take the first K element. \nmake a dp to store the number of times each category occured.\nif all the category are different for first k itself:\nreturn the (sum of profit for first k element) + k**2.\nelse:\nremove the element from last which are having more than one in dp.\nAlso parallely keep an look on ans. \nkeep on doing this either till you reach all distinct category or you go out of range.\n# Complexity\n- Time complexity: O(n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$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        dp={}\n        sm=0\n        for i in range(k):\n            dp[items[i][1]]=dp.get(items[i][1],0)+1\n            sm+=items[i][0]\n        ans= sm + (len(dp))**2\n        h=[]\n        for i in range(k):\n            h.append(items[i])\n        j=k\n        ln=len(dp)\n        while h and j<len(items):\n            x,y= h.pop()\n            if dp[y]==1:\n                continue\n            else:\n                sm-=x\n                dp[y]-=1\n                while j<len(items) and items[j][1] in dp:\n                    j+=1\n                if j<len(items):\n                    sm+= items[j][0]\n                    dp[items[j][1]]=1\n                    ln+=1\n            ans=max(ans,sm+ln**2)\n        return ans\n            \n            \n            \n        \n```
['Sorting', 'Python3']