🔥🔥Beats 99%✅Simple and Easy💯🔥Detailed Explanation🔥Sorting & Greedy🔥[Python, Java, C++ & JS]
\nSubmission link: Python, Java, C++ & JavaScript\n\n## \uD83C\uDFAF Problem Explanation:\nGiven an array happiness and a positive integer k, we need to select 
![image.png](https://assets.leetcode.com/users/images/a582f572-ce91-4e80-b11d-7abe79b3b111_1715215751.1679418.png)\nSubmission link: [Python](https://leetcode.com/problems/maximize-happiness-of-selected-children/submissions/1253079848?envType=daily-question&envId=2024-05-09), [Java](https://leetcode.com/problems/maximize-happiness-of-selected-children/submissions/1253081148?envType=daily-question&envId=2024-05-09), [C++](https://leetcode.com/problems/maximize-happiness-of-selected-children/submissions/1253082953?envType=daily-question&envId=2024-05-09) & [JavaScript](https://leetcode.com/problems/maximize-happiness-of-selected-children/submissions/1253083482?envType=daily-question&envId=2024-05-09)\n\n## \uD83C\uDFAF Problem Explanation:\nGiven an array `happiness` and a positive integer `k`, we need to select `k` children from `n` children standing in a queue, where each child has a happiness value `happiness[i]`. In each turn, selecting a child decreases the happiness value of all unselected children by 1. We are to maximize the sum of the happiness values of the selected children.\n\n## \uD83E\uDD14 Intuition:\nTo maximize the sum of happiness values, we should select children with the highest happiness values first. Sorting the `happiness` array in descending order allows us to select the highest happiness values first. And `decrement` value `happiness` for every iteration greedily.\n\n## \uD83E\uDDE0 Approach:\n1. Sort the `happiness` array in descending order.\n2. Initialize variables `decrement` and `result` to 0.\n3. While `k > 0` and the happiness value of the current child minus its index is greater than 0:\n    - Add the happiness value of the current child minus its index to the `result`.\n    - Decrement `k` and increment `decrement`.\n4. Return the `result`.\n\n## \u2699\uFE0F Dry Run:\n- Input: happiness = [1, 1, 1, 1], k = 2\n- Sorted happiness array: [1, 1, 1, 1]\n- decrement = 0, result = 0\n    - k = 2, happiness[0] - 0 = 1 > 0\n        - Add 1 to result: result = 1\n        - Decrement k: k = 1\n        - Increment decrement: decrement = 1\n    - k = 1, happiness[1] - 1 = 0 not > 0\n- Return result: 1\n\n# \uD83D\uDCD2 Complexity:\n- \u23F0 Time complexity: $$O(nlog(n))$$, nlog(n) for sorting and O(k) for iteration\n- \uD83E\uDDFA Space complexity: $$O(1)$$\n\n\n# Code\n``` python []\nclass Solution:\n    def maximumHappinessSum(self, happiness: List[int], k: int) -> int:\n        happiness.sort(reverse = True)\n        decrement, result = 0, 0\n        while (k > 0 and happiness[decrement]-decrement > 0):\n            result += happiness[decrement]-decrement\n            k, decrement = k-1, decrement+1\n        return result\n```\n``` java []\nclass Solution {\n    public long maximumHappinessSum(int[] happiness, int k) {\n        Arrays.sort(happiness);\n        long result = 0;\n        int n = happiness.length, decrement = 0;\n        while (k > 0 && happiness[n - 1 - decrement] - decrement > 0) {\n            result += happiness[n - 1 - decrement] - decrement;\n            k--;\n            decrement++;\n        }\n        return result;\n    }\n}\n```\n``` cpp []\nclass Solution {\npublic:\n    long long maximumHappinessSum(vector<int>& happiness, int k) {\n        sort(happiness.begin(), happiness.end(), greater<int>());\n        long long result = 0;\n        int decrement = 0;\n        while (k > 0 && happiness[decrement] - decrement > 0) {\n            result += happiness[decrement] - decrement;\n            k--;\n            decrement++;\n        }\n        return result;\n    }\n};\n```\n``` javascript []\nvar maximumHappinessSum = function(happiness, k) {\n    happiness.sort((a, b) => b - a);\n    let result = 0;\n    let decrement = 0;\n    while (k > 0 && happiness[decrement] - decrement > 0) {\n        result += happiness[decrement] - decrement;\n        k--;\n        decrement++;\n    }\n    return result;\n}\n```\n\n\n---\n# Please consider giving an Upvote!\n![upvote.png](https://assets.leetcode.com/users/images/5fbeecf2-18f6-4dce-a4a0-f11c859e46ad_1714711173.2665718.png)
['Greedy', 'Sorting', 'Python', 'C++', 'Java', 'Python3', 'JavaScript']