Simple Hash Table Solution
Intuition\n Describe your first thoughts on how to solve this problem. \nDp won\'t work with O(n^2) so choose greedy\nMaximize profit and distinct categories\n\
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nDp won\'t work with $$O(n^2)$$ so choose greedy\nMaximize profit and distinct categories\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nFirst maximize profit by selecting k max-profit elements, then check if elegance can be maximized by removing max-profit element of same category (within k elements) and including a profit with new category.\n\nYou may keep track of recurring categories and their elements.\n\nSquare of distinct category may overpower maxprofit so you have to check till the end.\n\n# Complexity\n- Time complexity: $$O(nlog 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 {\npublic:    \n    long long findMaximumElegance(vector<vector<int>>& items, int k) {\n        int n=items.size();\n        long long sum=0;\n        unordered_map<int,vector<int>>store;\n\n        sort(items.begin(),items.end());\n        reverse(items.begin(),items.end());\n\n        //maximize profit\n        for(int i=0;i<k;i++){\n            sum+=items[i][0];\n            store[items[i][1]].push_back(i);\n        }\n\n        //distinct categories\n        long long count=store.size();\n\n        if(k==n){\n            return sum+(count*count);\n        }\n\n        //to compare new elegance by including distinct category\n        int i=k-1,j=k;\n        long long tempsum=sum;\n        int newcount=count;\n\n        //traverse till end\n        while(i>=0){\n            if(store[items[i][1]].size()==1){\n                i--;\n            }\n            else{\n                tempsum-=items[i][0];\n\n                //find distinct category\n                while(j<n&&store.find(items[j][1])!=store.end()){\n                    j++;\n                }\n                if(j==n){\n                    return sum+(count*count);\n                }\n\n                //calculate new elegance\n                tempsum+=items[j][0];\n                newcount+=1;\n\n                store[items[j][1]].push_back(j);\n                store[items[i][1]].pop_back(); \n                j++;i--; \n\n                if(tempsum+(newcount*newcount)<=sum+(count*count)){\n                    //if new elegance is still less than previous\n                    continue;\n                }\n                else{\n                    //new elegance is greater\n                    sum=tempsum;\n                    count=newcount;           \n                }\n            }\n            \n        }  \n\n        return sum+(count*count);      \n    }\n};\n```
['Hash Table', 'Greedy', 'Sorting', 'C++']