Swift: Beats 100% || TC - O(n * log n) || SC - O(n)
Approach\n1. Arrange items by profits in decreasing order.\n2. Sum k most profitable items in sorted array.\n3. After kth item check if we have visited any dupl
# Approach\n1. Arrange items by profits in decreasing order.\n2. Sum `k` most profitable items in sorted array.\n3. After `k`th item check if we have visited any duplicate category. If no then we have already visited `k` most profitable items with unique categories. We have found our answer.\n4. If we have visited duplicate categories, then remove least profitable item from duplicate category and current item\'s profit. Then recalculate answer.\n\n# Complexity\n- Time complexity: O(n * log n)\n- Space complexity: O(n)\n\n# Code\n```swift []\nclass Solution {\n    func findMaximumElegance(_ items: [[Int]], _ k: Int) -> Int {\n        // Sort by profit in decreasing order\n        var sortedItems = items.sorted { $0[0] > $1[0] }\n\n        var seenCategories: Set<Int> = []\n        var duplicateCategoryProfits: [Int] = []\n        var currentElegance: Int = 0\n        var maxElegance: Int = 0\n\n        for (i, item) in sortedItems.enumerated() {\n            if i < k { // we have not yet visited minimim k most profitable items, so add them\n\n                if seenCategories.contains(item[1]) {\n                    // we encountered item category from previously visited category\n                    duplicateCategoryProfits.append(item[0])\n                }\n\n                currentElegance += item[0]\n            } else {\n                if duplicateCategoryProfits.isEmpty {\n                    // we have visited k most profitable items with unique categories\n                    // following items will yield lower profits so no need to calculate more\n                    break\n                }\n\n                if !seenCategories.contains(item[1]) {\n                    // remove minimum profit from duplicate category\n                    // as we already sorted the array in decreasing profit\n                    // minimum one will be last added item;\n                    currentElegance -= duplicateCategoryProfits.removeLast()\n\n                    // and then add current item\'s profit\n                    currentElegance += item[0]\n                }\n            }\n\n            // mark category as visited\n            seenCategories.insert(item[1])\n            maxElegance = max(\n                maxElegance,\n                currentElegance + (seenCategories.count * seenCategories.count)\n            )\n        }\n\n        return maxElegance\n    }\n}\n```
['Array', 'Hash Table', 'Swift', 'Sorting']