Fastest (100%) || Short & Concise || Easiest to Understand
Intuition\nIt\'s like picking the tastiest ramen bowls from a buffet, starting with the yummiest, within a limit, ensuring each bowl adds to your overall satisf
# Intuition\nIt\'s like picking the tastiest ramen bowls from a buffet, starting with the yummiest, within a limit, ensuring each bowl adds to your overall satisfaction!\n\n# Approach\n\nSo, the problem aims to maximize the total happiness gained by selecting the happiest bowls of ramen within the given budget (`k`). It\'s all about enjoying the most happiness while savoring some tasty ramen! Let\'s break down the approach used in the code with Yuji Itadori\'s style:\n\n1. **Sorting the Happiness Bowls**: Just like picking the most delicious ramen bowls, we sort the bowls of happiness in descending order. This way, we can start with the happiest ones first!\n\n2. **Eating the Yummiest Bowls**: With a limited number of bowls we can eat (`k`), we start devouring the yummiest ones! Each time we eat a bowl, we check if it makes us even happier. If it does, we enjoy it; otherwise, we skip it.\n\n3. **Adjusting Happiness Levels**: As we eat the bowls, we also adjust the happiness levels of the remaining bowls. We subtract 1 from their happiness, but only if they were initially positive.\n\n4. **Summing Up the Joy**: After finishing our ramen feast, we sum up all the happiness from the bowls we\'ve eaten. That\'s our total joy!\n\nSo, it\'s all about picking the most happiness-packed bowls within our limit and making sure each bowl we eat adds to our overall joy. Just like enjoying a hearty ramen meal!\n\n\n\n**Dry - Run :**\nLet\'s go through the dry run for the given example:\n\n```\nInput: happiness = [1, 2, 3], k = 2\n```\n\n**Step 1:** Sort the `happiness` array in descending order.\n\n```\nhappiness = [3, 2, 1]\n```\n\n**Step 2:** Initialize variables.\n\n```cpp\ni = 0\nres = 0\n```\n\n**Step 3:** Enter the loop toselect `k` children.\n\n```cpp\nwhile(k--) {\n    // k = 2\n    happiness[i] = max(happiness[i] - i, 0);\n    // happiness[0] = max(3 - 0, 0) = 3\n\n    res += happiness[i++];\n    // res = 0 + 3 = 3\n    // i = 1\n\n    // k = 1\n    happiness[i] = max(happiness[i] - i, 0);\n    // happiness[1] = max(2 - 1, 0) = 1\n\n    res += happiness[i++];\n    // res = 3 + 1 = 4\n    // i = 2\n}\n```\n\nSince `k` is now 0, the loop terminates.\n\n**Step 4:** Return the result.\n\n```cpp\nreturn res; // Returns 4\n```\n\nSo, the maximum sum of happiness values by selecting 2 children is 4, which is achieved by:\n\n1. Selecting the child with the maximum happiness value of 3. The remaining happiness values become `[0, 1]`.\n2. Selecting the child with the happiness value of 1. The remaining happiness value becomes `[0]`.\n\nThe sum of the happiness values of the selected children is 3 + 1 = 4, as mentioned in the explanation.\n\n# Complexity\n- Time complexity: O(nlogn + min(k, n))\n\n- Space complexity: O(1)\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    long long maximumHappinessSum(vector<int>& happiness, int k) {\n        ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);\n        sort(begin(happiness), end(happiness), greater<int>());\n        int i = 0;\n        long long res = 0;\n\n        while(k--) {\n            happiness[i] = max(happiness[i] - i, 0);\n            res += happiness[i++];\n        }\n\n        return res;\n    }\n};\n```\n```java []\npublic class Solution {\n    public long maximumHappinessSum(int[] happiness, int k) {\n        Arrays.sort(happiness);\n        long res = 0;\n        int n = happiness.length, j = 0;\n\n        for (int i = n - 1; i >= n - k; --i) {\n            happiness[i] = Math.max(happiness[i] - j++, 0);\n            res += happiness[i];\n        }\n\n        return res;\n    }\n}\n```\n```python []\nclass Solution:\n    def maximumHappinessSum(self, happiness: List[int], k: int) -> int:\n        happiness.sort(reverse=True)\n        i = 0\n        res = 0\n\n        while k > 0:\n            happiness[i] = max(happiness[i] - i, 0)\n            res += happiness[i]\n            i += 1\n            k -= 1\n\n        return res\n```\n```javascript []\n/**\n * @param {number[]} happiness\n * @param {number} k\n * @return {number}\n */\nvar maximumHappinessSum = function(happiness, k) {\n    happiness.sort((a, b) => b - a);\n    let i = 0;\n    let res = 0;\n\n    while (k > 0 && i < happiness.length) {\n        happiness[i] = Math.max(happiness[i] - i, 0);\n        res += happiness[i];\n        i++;\n        k--;\n    }\n\n    return res;\n};\n```\n![yuji.jpeg](https://assets.leetcode.com/users/images/5a140f72-d0ff-4ca7-bc88-234458c9febc_1715214613.5368502.jpeg)\n
['Array', 'Greedy', 'Sorting', 'C++', 'Java', 'Python3', 'JavaScript']