Warning | Don't watch this | 😓
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:$$O(n*log(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```\nimport java.util.*;\n\nclass Solution {\n    public long findMaximumElegance(int[][] items, int k) {\n        \n        int[][] pairs = new int[items.length][2];\n        \n        // Transform items into pairs with (category, profit)\n        for (int i = 0; i < items.length; i++) {\n            pairs[i][0] = items[i][1];\n            pairs[i][1] = items[i][0];\n        }\n        \n        // Sort pairs by profit in descending order\n        Arrays.sort(pairs, (p1, p2) -> p2[1] - p1[1]);\n\n        long maxRes = -(long)1e9;\n\n        // TreeMap to maintain pairs of (category, profit) with their frequencies, sorted by profit, then category\n        TreeMap<int[], Integer> maxProfits = new TreeMap<>((a, b) -> {\n            if (a[1] != b[1]) return Integer.compare(a[1], b[1]);\n            return Integer.compare(a[0], b[0]);\n        });\n\n        // Map to store a PriorityQueue of profits for each category\n        Map<Integer, PriorityQueue<Integer>> catProfits = new HashMap<>();\n        long res = 0;\n        Set<Integer> distinctCats = new HashSet<>();\n\n        for (int i = 0; i < pairs.length; i++) {\n            int[] pair = pairs[i];\n            int cat = pair[0];\n            int profit = pair[1];\n\n            if (distinctCats.size() == k) break;\n\n            if (i < k) {\n                res += profit;\n                distinctCats.add(cat);\n                maxRes = Math.max(maxRes, res + (long)distinctCats.size() * distinctCats.size());\n                \n            } else {\n                if (!distinctCats.contains(cat)) {\n\n                    Map.Entry<int[], Integer> minPairEntry = maxProfits.firstEntry();\n                    int[] minPair = minPairEntry.getKey();\n                    int removedCat = minPair[0];\n                    int removedProfit = minPair[1];\n                    if (minPairEntry.getValue() == 1) {\n                        maxProfits.pollFirstEntry();\n                    } else {\n                        maxProfits.put(minPair, minPairEntry.getValue() - 1);\n                    }\n                    \n                    distinctCats.add(cat);\n\n                    res = res - removedProfit + profit;\n                    maxRes = Math.max(maxRes, res + (long)distinctCats.size() * distinctCats.size());\n\n                    PriorityQueue<Integer> pq = catProfits.get(removedCat);\n                    pq.poll();\n                    if (pq.size() == 1) {\n                        int remainingProfit = pq.peek();\n                        maxProfits.put(new int[]{removedCat, remainingProfit}, maxProfits.getOrDefault(new int[]{removedCat, remainingProfit}, 0) - 1);\n                        if (maxProfits.get(new int[]{removedCat, remainingProfit}) == 0) {\n                            maxProfits.remove(new int[]{removedCat, remainingProfit});\n                        }\n                    }\n                    catProfits.put(removedCat, pq);\n                }\n            }\n         \n            if (i < k || !distinctCats.contains(cat)) {\n                PriorityQueue<Integer> pq = catProfits.getOrDefault(cat, new PriorityQueue<>());\n                pq.offer(profit);\n                catProfits.put(cat, pq);\n                PriorityQueue<Integer> updatedPq = catProfits.get(cat);\n                \n                if (updatedPq.size() == 1) continue;\n\n                if (updatedPq.size() == 2) {\n                    int p1 = updatedPq.poll();\n                    int p2 = updatedPq.poll();\n                    maxProfits.put(new int[]{cat, p1}, maxProfits.getOrDefault(new int[]{cat, p1}, 0) + 1);\n                    maxProfits.put(new int[]{cat, p2}, maxProfits.getOrDefault(new int[]{cat, p2}, 0) + 1);\n                    updatedPq.offer(p1);\n                    updatedPq.offer(p2);\n                    catProfits.put(cat, updatedPq);\n                } else {\n                    maxProfits.put(new int[]{cat, profit}, maxProfits.getOrDefault(new int[]{cat, profit}, 0) + 1);\n                }\n            }\n        }\n\n        return maxRes;\n    }\n}\n```
['Hash Table', 'Ordered Map', 'Heap (Priority Queue)', 'Java']