Greedy || Count Duplicates || Sorting
Intuition\nThe test case : [1,2,3,4] gives an idea to solve this problem. It\'s answer is 3, or something to do with the sorted array arrangement. If the array 
# Intuition\nThe test case : $$[1,2,3,4]$$ gives an idea to solve this problem. It\'s answer is $$3$$, or something to do with **the sorted array** arrangement. If the array had no duplicate elements, the answer would always be= **the number of elements -1** .Simple logic being, the greatest number[$$4$$ in the above array considered] in the array cannot be matched with any number, but everybody else can be. That is how we arrive to our answer.\n\n# Approach\nConsider the arrays: \n-$$[1,1,1,1,1,2,3,4]$$\nThe answer is $$3$$. The addition of additional $$1s$$ does not affect our answer, as we can match each $$1$$ with a $$1$$\n\n---\n\n\nConsider the array in test case 1 in sorted order:\n$$[1,1,1,2,3,3,5]$$ and notice that it has the same arrangement:\n$$[3,3,5]$$, which has an answer of $$2$$. The benefit in this case is though, we get an additional $$3$$ that we can match with one of the $$1$$ in the array. That is how the presence of duplicates will give us a greater answer than just the number of distinct elements in the array. \n\nIf we **sort** the array, we will always have this subproblem: \n$$[x,x,x,x,x,x+1,]$$ \n# It is akin to an array of $$[x,x+1]$$, we just get spare elements(x) that we can use to match with duplicates of numbers smaller than x\n\nOr if you **keep a count of numbers** that are greater than $$x$$, you can tabulate your result. \n\n# Complexity\n- Time complexity:\n$$O(n log n)$$\n\n- Space complexity:\n$$O(n)$$ \n\n# Code\n```Java []\nclass Solution {\n    public int maximizeGreatness(int[] nums) {\n        Arrays.sort(nums);\n        int n=nums.length;\n        int ans=0;\n        int rem=0; //Numbers greater than the current number\n        int curem=0; //Numbers equal to the current number\n        int comp= nums[n-1]; //The last greatest number we have encountered so far\n        for(int i=n-2;i>=0;i--){\n            if(nums[i]<comp){ //[3,4] we are checking 3 here\n                comp=nums[i]; //found a new guy\n                rem+=curem;  //include the number of 3s in our\n                            //numbers greater than nums[i] counter\n                curem=0;  //Reset the count of numbers same as nums[i]\n                ans++;\n            }\n            else if(nums[i]==nums[i+1]) {  \n                if(rem>0){ //if there is a spare number above, incrememnt sum \n                    rem--;\n                    ans++;\n                }\n                curem++; //this number cannot be paired, but we can use it later\n            }\n        }\n        return ans;\n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    int maximizeGreatness(vector<int>& nums) {\n        sort(nums.begin(), nums.end());\n        int n=nums.size();\n        int ans=0;\n        int rem=0; //Numbers greater than the current number\n        int curem=0; //Numbers equal to the current number\n        int comp= nums[n-1]; //The last greatest number we have encountered so far\n        for(int i=n-2;i>=0;i--){\n            if(nums[i]<comp){ //[3,4] we are checking 3 here\n                comp=nums[i]; //found a new guy\n                rem+=curem;  //include the number of 3s in our\n                            //numbers greater than nums[i] counter\n                curem=0;  //Reset the count of numbers same as nums[i]\n                ans++;\n            }\n            else if(nums[i]==nums[i+1]) {  \n                if(rem>0){ //if there is a spare number above, incrememnt sum \n                    rem--;\n                    ans++;\n                }\n                curem++; //this number cannot be paired, but we can use it later\n            }\n        }\n        return ans;\n    }\n};\n\n```\n```Python3 []\nclass Solution:\n    def maximizeGreatness(self, nums: List[int]) -> int:\n        nums.sort()\n        n=len(nums)\n        ans=0\n        rem=0 #Numbers greater than the current number\n        curem=0 #Numbers equal to the current number\n        comp= nums[n-1] #The last greatest number we have encountered so far\n        for i in range(n-2,-1,-1):\n            if(nums[i]<comp): #[3,4] we are checking 3 here\n                comp=nums[i] #found a new guy\n                rem+=curem #include the number of 3s in our numbers greater than nums[i] counter\n                curem=0 #Reset the count of numbers same as nums[i]\n                ans+=1\n            elif(nums[i]==nums[i+1]): \n                if(rem>0): #if there is a spare number above, incrememnt sum \n                    rem-=1\n                    ans+=1\n                curem+=1 #this number cannot be paired, but we can use it later\n        return ans\n\n```\n
['C++', 'Java', 'Python3']