Full problem breakdown and explaination
IntuitionFirst lets consider a simple case of this problem: [1,2,3,4]. This list has the solution of 3 for this problem. Why? Becuase every value but 4 has a va
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nFirst lets consider a simple case of this problem: [1,2,3,4]. This list has the solution of 3 for this problem. Why? Becuase every value but 4 has a value that is greater than itself, thus we know we can simply shift the list over to create a valid permutation with a greatness value of 3 ([2,3,4,1]). \n\nWe also understand that if we disorder the same list ([2,4,1,3]) the greatness will still be the same value. This is becuase we can always change how our permutation is ordered to match in the same way it did before ([3,1,2,4]).\n\nNow we must consider the case where the list contains repeated elements: [1,2,3,4,1,2,3,4]. In this case we can visibly see that the answer is 6. We see this by understanding that the first four elements in the list are exactly like before with the answer of 3 and the following four elements are the exact same with also the answer of 3 ([1,2,3,4] and [1,2,3,4]), summing to 6. This may lead some to incorrectly assume that we can break up the incomming list however we want, however this is not the case. If we broke this set up a different way ([1,2,3] and [4,1,2,3,4]) and sum the greatness of both of these lists we get the answer 5 not 6. So what makes the first case so special? In the first case both lists are entirly unique is the smallest number of possible sets that can be created from the list (e.g. [1,2,3], [1,2,3,4], [4] is still invalid). Thus if the incomming list was [1,2,3,4,1,2,1,2,3,4,1,2,1,2,3] it can be broken up into: [1,2,3,4], [1,2], [1,2,3,4], [1,2], [1,2,3] and if the greatness of each of these sets is taken and summed, we get the greatness of the orignial list.\n\nSo then how do we get the number of unique sets that can be made from any list? Becuase each set must contain at least one of every value and values cannot be repeated in any set, it follows that the lowest number of sets is equvalent to the frequency of the most repeated value, i.e. the mode.\n\n### Main Takeaway:\n1. An entirely unique set of values will always have the greatness of the length of the set minus one.\n2. Greatness does not depend on the order of the list.\n3. The greatness of any list is the sum of the greatness of the smallest number of unique sets that the original list can be broken down into.\n4. The smallest number of unique sets that can be made from any list is equivalent to the frequency of the mode of the list.\n\n***Putting it all together we understand that the greatness of any list is equivalent to the length of the list minus the frequency of its mode.***\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nSolving for the frequency of the mode is a fairly trivial problem. Simply define a hash map using the incomming values as keys and increment each time the value is called and at the end take the highest value. From there simply subtract that value from the length of the list to get the maximum greatness.\n\n# Complexity\n- Time complexity: $$O(n)$$\nWe only need to loop once through the values to find the frequency of the mode.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\nIn the worst case the resulting hashmap generated will use 2N values, making the space complexity $$O(N)$$.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int maximizeGreatness(vector<int>& nums){\n        unordered_map<int, int> frequency;\n        int length = 0;\n        int maxCount = 0;\n        for (int num : nums) {\n            if(maxCount < ++frequency[num]) maxCount++;\n        }\n\n        return nums.size() - maxCount;\n    }\n};\n```
['C++']