[C/C++/Python] Detailed description and comments. O(nlogn) time, O(n) space
Intuition\nThe problem calls for picking the best of two disconnected values, the number of categories and the total of the profits. My immediate thought was th
# Intuition\nThe problem calls for picking the best of two disconnected values, the number of categories and the total of the profits. My immediate thought was that starting at one extreme and working towards the other will produced the answer.\n\nStart with maximising the profits by selecting the _k_ most profitable as a base case. Then by definition, swapping out any item by a new item in a as yet unused category, will decrease the total profits, but increase the number of unique categories.\n\n# Approach\nCalculate the initial maximum profit state.\n* Sort _items_ from highest profit to lowest profit\n* Calculate the profits of the first _k_ items while also recording how many of those _k_ items are in each category.\n\nFrom here there is no point swapping one item for a later item unless a new category has been added. Thus the next step is to progressively find the least profitable item in our existing items from a category that has more than one item and swap it with the most profitable item in a new category. This will _decrease_ total profits, but _increase_ the total number of categories.\n\n# Complexity\n- Time complexity: $$O(nlog_2n)$$\n    - $$O(nlog_2n)$$ for the sort\n    - $$O(n)$$ trying to swap each unused item in\n\n- Space complexity: $$O(n)$$\n    - $$O(n)$$ to hold a sorted copy of _items_\n    - $$O(n)$$ to hold a count of items in each category.\n\n# Code\n``` python []\ndef findMaximumElegance(self, items: List[List[int]], k: int) -> int:\n  sort = sorted(items, key=lambda arr: arr[0], reverse=True)\n  \n  # Calculate the initial state using the k most profitable items\n  curr = 0\n  categories = dict()\n  for item in sort[:k]:\n    curr += item[0]\n    if item[1] in categories:\n      categories[item[1]] += 1\n    else:\n      categories[item[1]] = 1\n  ret = curr + len(categories) ** 2\n\n  # The only way to increase further than this is to increase the number of categories\n  # as from above, any other item will have less profits. Thus only swapping an item\n  # from a category which we have more than one item for, for an item in a new category\n  # will increase the number of unique categories to offset the decrease in total profit.\n  option_idx = k\n  for item_idx in range(k - 1, 0, -1):\n    if 1 == categories[sort[item_idx][1]]:\n      # Only one item of this category, swapping it would not increase the number of categories\n      continue\n    categories[sort[item_idx][1]] -= 1\n\n    # Find the first new category if there is one\n    while option_idx < len(sort) and sort[option_idx][1] in categories:\n      option_idx += 1\n\n    if option_idx < len(sort):\n      # Try swapping the new item with the least profitable\n      curr += -sort[item_idx][0] + sort[option_idx][0]\n      categories[sort[option_idx][1]] = 1\n      ret = max(ret, curr + len(categories) ** 2)\n\n  return ret\n```\n``` cpp []\nlong long findMaximumElegance(vector<vector<int>>& items, int k) {\n  // Sort the items from highest profit to lowest\n  std::vector<std::reference_wrapper<std::vector<int>>> sorted{std::begin(items), std::end(items)};\n  std::sort(\n      std::begin(sorted),\n      std::end(sorted),\n      [] (const std::vector<int>& lhs, const std::vector<int>& rhs) { return lhs[0] > rhs[0]; });\n\n  // Calculate the initial state using the k most profitable items\n  long long curr = 0;\n  std::unordered_map<int, int> categories;\n  for (int i = 0; i < k; ++i) {\n    const std::vector<int>& item = sorted[i];\n    curr += item[0];\n    ++categories[item[1]];\n  }\n  long long ret = curr + categories.size() * categories.size();\n\n  // The only way to increase further than this is to increase the number of categories\n  // as from above, any other item will have less profits. Thus only swapping an item\n  // from a category which we have more than one item for, for an item in a new category\n  // will increase the number of unique categories to offset the decrease in total profit.\n  auto option_idx = k;\n  for (auto item_idx = k - 1; 0 < item_idx; --item_idx) {\n    const std::vector<int>& item = sorted[item_idx];\n    if (1 == categories[item[1]]) {\n      // Only one item of this category, swapping it would not increase the number of categories\n      continue;\n    }\n    --categories[item[1]];\n\n    // Find the first new category if there is one\n    while (option_idx < sorted.size() && categories.count(sorted[option_idx].get()[1])) {\n      ++option_idx;\n    }\n\n    if (option_idx < sorted.size()) {\n      // Try swapping the new item with the least profitable\n      const std::vector<int>& option_item = sorted[option_idx++];\n      curr += -item[0] + option_item[0];\n      ++categories[option_item[1]];\n      ret = std::max<long long>(ret, curr + categories.size() * categories.size());\n    }     \n  }\n\n  return ret;\n}\n```\n\n``` c []\nstruct category_hash {\n  int category;\n  int count;    /* Number of items included with this category */\n  UT_hash_handle hh;\n};\n\nstatic\nint pair_cmp(const void* l, const void* r) {\n  const int* lhs = *(const int**) l;\n  const int* rhs = *(const int**) r;\n  return rhs[0] - lhs[0];\n}\n\nstatic\nlong long llmax(long long a, long long b) { return a > b ? a : b; }\n\nlong long findMaximumElegance(int** items, int itemsSize, int* itemsColSize, int k){\n  /* Hashtable to hold a count of the number of items in use by each category */\n  struct category_hash* table = NULL;\n  struct category_hash entries[itemsSize];\n  struct category_hash* pos = entries;\n\n  /* Build a set of items sorted from highest profit to lowest */\n  int* sorted[itemsSize];\n  memcpy(sorted, items, itemsSize * sizeof(*items));\n  qsort(sorted, itemsSize, sizeof(*sorted), &pair_cmp);\n\n  /* Start by choosing all the highest profit items and building a set of the minimal number of categories */\n  long long curr = 0;\n  for (int i = 0; i < k; ++i) {\n    curr += sorted[i][0];\n    struct category_hash* entry;\n    HASH_FIND_INT(table, &sorted[i][1], entry);\n    if (!entry) {\n      entry = pos++;\n      entry->category = sorted[i][1];\n      entry->count = 0;\n      HASH_ADD_INT(table, category, entry);\n    }\n    ++entry->count;\n  }\n\n  long long categories = HASH_COUNT(table);\n  long long ret = curr + categories * categories;\n\n  /*\n  The only way to increase further than this is to increase the number of categories\n  as from above, any other item will have less profits. Thus only swapping an item\n  from a category which we have more than one item for, for an item in a new catefory\n  will increase the number of unique categories.\n  */\n  int idx = k;\n  for (int i = k - 1; 0 < i; --i) {\n    struct category_hash* entry;\n    HASH_FIND_INT(table, &sorted[i][1], entry);\n    if (1 == entry->count) {\n      /* Only one item of this category, swapping it would not increase the number of categories */\n      continue;\n    }\n    --entry->count;\n\n    /* Find the first new category if there is one */\n    while (idx < itemsSize) {\n      HASH_FIND_INT(table, &sorted[idx][1], entry);\n      if (entry) {\n        ++idx;\n        continue;\n      }\n\n      /* New category has been found, add it to the set of categories now */\n      entry = pos++;\n      entry->category = sorted[idx][1];\n      entry->count = 1;\n      HASH_ADD_INT(table, category, entry);\n      break;\n    }\n\n    if (idx < itemsSize) {\n      /* Try swapping the least profitable with our new choice */\n      curr += -sorted[i][0] + sorted[idx][0];\n      ++categories;\n      ret = llmax(ret, curr + categories * categories);\n    }\n  }\n\n  /* Destroy the hashtable and return the final result */\n  HASH_CLEAR(hh, table);\n  return ret;\n}\n```\n
['C', 'Python', 'C++', 'Python3']