✅✅97.44% with Java🔥Beginner Friendly🔥Simple Logic🔥Easy Explanation🔥
\n\n# Intuition\n Describe your first thoughts on how to solve this problem. \nWe have to maximize the happiness of selected children. From the name itself, we 
![Images.png](https://assets.leetcode.com/users/images/d8348d79-a87c-4fde-a368-11bf810fa077_1715233362.6762805.png)\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe have to `maximize` the happiness of selected children. From the name itself, we can conclude that it is a `Greedy Problem`.\nNo need to fear from the name, as the explaination will be easy\uD83D\uDE09.\n\nBut we have to keep the following points in the mind:\n\n    1. We have to select k children with maximum happiness.\n    2. If we select a child, then we cannot reselect it again.\n    3. Each time we select a child, happiness of other\n       children decrease by 1.\n    4. Happiness of a child cannot go below 0.\nAfter keeping these points in mind, we are ready to understand the approach of this question.\n\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe can follow the below steps to approach this problems:\n\n    Step-1: Sort the array.\n    Step-2: Create a variable max_happiness that store our answer.\n    Step-3: Create a variable minus_meter that check how much happiness\n           we have to substract from the current child.\n    Step-4: Iterate over the array from last to first index untill k\n            selections are made.\n    Step-5: For each child, calculate happiness and add it to answer.\nFinally, return the `max_happiness.`\n\n# Explanation\n$$Step1: $$ We sort the array as we want maximum happiness in each iteration.\n$$Step2: $$ The answer is updated in each iteration so we need a variable to store it.\n$$Step3: $$ In each iteration, we will select a child with maximun happiness but the\nhappiness of other children will decrease by 1. \nSo, we can say that,\n        \n`After 1st iteration: happiness of rest children decreased by a total of 1.`\n`After 2nd iteration: happiness of rest children decreased by a total of 2.`\n`After 3rd iteration: happiness of rest children decreased by a total of 3.`\nand so on.\nSo, we need a variable minus_meter to store how much value we need to subtract from each child to find the current_max_happiness.\n\n$$Step4: $$ We iterate from last index as the array is sorted in non-decreasing order(ascending order), so the maximum happiness will be at the last.\n\n $$Step5: $$ We will calculate the current_max_happiness by subtracting the minus_meter and also checking it does not go negative. And then we add in maximum_happiness.\n\nFinally, we will the return the maximum_happines.\n\n\n# Complexity\n- Time complexity: $$O(NlogN)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(1)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nThe actual time to complete the program is O(NlogN) (sorting time) + O(N) (Loop time).\nSo, the time complexity becomes O(NlogN).\nWe, are not using any external space so, space complexity is O(1).\n\n![upvoteeeee.png](https://assets.leetcode.com/users/images/73b366e5-8942-48ea-bd49-81c182bc6f46_1707401769.2975633.png)\n\n# Code\n\n```java []\nclass Solution {\n    public long maximumHappinessSum(int[] happiness, int k) {\n\n        // Step-1                \n        Arrays.sort(happiness);\n\n        // Step-2\n        long max_happiness = 0;\n\n        // Step-3\n        int minus_meter = 0;\n\n        // Step-4\n        for(int i = happiness.length-1; i >= 0 && k > 0; i--)\n        {\n            // Step-5\n            int current_max_happiness = happiness[i] - minus_meter;\n            if(current_max_happiness < 0)\n            {\n                current_max_happiness = 0;\n            }\n            max_happiness += current_max_happiness;\n\n            // Increment minus_meter in each iteration.\n            minus_meter++;\n\n            // Derement k after each selection.\n            k--;\n        }\n\n        return max_happiness;        \n    }\n}\n```\nTerms and Conditions:\nIt beat 97% in the first attempt, but when I submitted it again, it only beat 51%. I don\'t know why it happened. That\'s why I am mentioning it here.\nPlease notice the top picture - it took 34 ms in first attempt.\nNow it is taking 35 ms. The difference of 1 ms can create such a huge difference.
['Greedy', 'Java']