💯Faster✅💯Lesser✅2 Methods🧠Detailed Approach🎯Greedy🔥Heap🔥Python🐍Java☕C++😎
\uD83D\uDE80 Hi, I\'m Mohammed Raziullah Ansari, and I\'m excited to share 2 ways to solve this question with detailed explanation of each approach:\n\n# \uD83C
# \uD83D\uDE80 Hi, I\'m [Mohammed Raziullah Ansari](https://leetcode.com/Mohammed_Raziullah_Ansari/), and I\'m excited to share 2 ways to solve this question with detailed explanation of each approach:\n\n# \uD83C\uDFAFProblem Explaination: \nYou are given an array `happiness` representing the happiness values of n children standing in a queue, and a positive integer k representing the number of turns you can select children.\n\nIn each turn, you select one child from the queue. When a child is selected, the happiness value of all children who have not been selected decreases by 1, but only if their happiness value is currently positive.\n\nYour task is to maximize the sum of the happiness values of the selected children by strategically choosing which children to select in each turn.\n\n### \uD83D\uDCE5Input:\n- `happiness`: An array of length n representing the happiness values of n children.\n- `k`: A positive integer representing the number of turns you can select children.\n\n### \uD83D\uDCE4Output:\n- Return an integer representing the maximum sum of the happiness values of the selected children.\n\n# \uD83D\uDD0D Methods To Solve This Problem:\nI\'ll be covering two different methods to solve this problem:\n1. Greedy Method\n2. Using Priority Queue\n\n# 1\uFE0F\u20E3 Greedy Method: \n\n### \uD83E\uDDE0Intuition:\nThe objective is to maximize the total happiness sum by selecting children with the highest happiness values. A logical strategy is to prioritize choosing children with the highest happiness values first, considering that the happiness of unselected children decreases over time.\n\nBy selecting children with the highest happiness values initially, we ensure that we capture the maximum happiness before it potentially decreases. This greedy approach aims to maximize short-term happiness gains by locking in the largest happiness scores early on.\n\nTo justify the optimality of this greedy approach, let\'s assume there exists an optimal solution where, for a given turn, the selected child\'s happiness value is not the ith largest in the array. If we swap this selected child with one of the higher happiness values, we would inevitably increase the total happiness sum. Therefore, the greedy approach of selecting the top k happiness scores from the array guarantees the highest possible total happiness sum.\n\nIn summary, adopting a greedy strategy to select the k children with the highest happiness values from the given array maximizes the overall happiness sum, as it captures the most significant happiness gains upfront.\n\n### \uD83D\uDCDADetailed Approach:\n1. **Sort the List in Descending Order:** To efficiently select the children with the highest happiness values, we sort the list of happiness values in descending order.\n\n2. **Initialize Variables:** Initialize `total_happiness_sum` to keep track of the sum of happiness values of the selected children. Initialize `turns` to keep track of the number of turns taken.\n\n3. **Iterate for K Turns:** We iterate for k turns, where in each turn, we:\n   - Access the happiness value of the child at index i (where i ranges from 0 to k-1 due to sorting).\n   - Decrement the happiness value by the number of turns taken so far. This accounts for the decrement in happiness for all unselected children.\n   - Add the adjusted happiness value to `total_happiness_sum`. Ensure that negative happiness values are not considered by taking the maximum of 0 and the computed value.\n   - Increment the `turns` variable to prepare for the next iteration.\n\n4. **Return Total Happiness Sum:** After k turns, return the total happiness sum, which represents the maximum sum of happiness values achievable by selecting k children.\n\n<!-- # Complexity\n- \u23F1\uFE0F Time Complexity: `O(n)` where n is the number of pairs in the list.\n -->\n<!-- - \uD83D\uDE80 Space Complexity: `O(n)` for the HashSet. -->\n\n# Code\uD83D\uDC68\uD83C\uDFFB\u200D\uD83D\uDCBB:\n```Python []\nclass Solution:\n    def maximumHappinessSum(self, happiness: List[int], k: int) -> int:\n        # Sort in descending order\n        happiness.sort(reverse=True)\n\n        total_happiness_sum = 0\n        turns = 0\n\n        # Calculate the maximum happiness sum\n        for i in range(k):\n            # Adjust happiness and ensure it\'s not negative\n            total_happiness_sum += max(happiness[i] - turns, 0)\n\n            # Increment turns for the next iteration\n            turns += 1\n\n        return total_happiness_sum\n```\n```Java []\nclass Solution {\n    public long maximumHappinessSum(int[] happiness, int k) {\n        int happinessSize = happiness.length;\n        \n        // Convert the array to an Integer array for sorting in descending order\n        Integer[] happinessArray = new Integer[happinessSize];\n        for(int i = 0; i < happinessSize; i++) {\n            happinessArray[i] = happiness[i];\n        }\n        \n        Arrays.sort(happinessArray, Collections.reverseOrder());\n\n        long totalHappinessSum = 0;\n        int turns = 0;\n        \n        // Calculate the maximum happiness sum\n        for(int i = 0; i < k; i++) {\n            // Adjust happiness and ensure it\'s not negative\n            totalHappinessSum += Math.max(happinessArray[i] - turns, 0);  \n\n             // Increment turns for the next iteration\n            turns++; \n        }\n        \n        return totalHappinessSum;\n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    long long maximumHappinessSum(vector<int>& happiness, int k) {\n        // Sort in descending order\n        sort(happiness.begin(), happiness.end(), greater<int>());\n        \n        long long totalHappinessSum = 0;\n        int turns = 0;\n        \n        // Calculate the maximum happiness sum\n        for(int i = 0; i < k; i++) {\n            // Adjust happiness and ensure it\'s not negative\n            totalHappinessSum += max(happiness[i] - turns, 0);  \n\n            // Increment turns for the next iteration\n            turns++; \n        }\n        \n        return totalHappinessSum;\n    }\n};\n```\n\n# 2\uFE0F\u20E3  Using Priority Queue:\n### \uD83E\uDDE0Intuition:\nIn our problem, maximizing total happiness relies on selecting the largest available element at each turn. This makes the choice of data structure crucial, and the max heap is particularly well-suited for this purpose. With a max heap, the largest element is always at the top, ensuring efficient access in alignment with our greedy algorithm\'s strategy of selecting the highest happiness value available at each turn.\n\nThe approach begins by constructing a max heap using all values from the happiness array. Then, for each of the k turns, we remove the maximum value from the heap. This ensures that we\'re consistently selecting the child with the highest happiness value at each turn. \n\nAfter removal, we adjust this value by subtracting the number of turns completed so far. This adjustment accounts for the decrease in happiness of the children who haven\'t been selected yet. Finally, we add this adjusted value to our total happiness sum.\n\nBy retaining its greedy nature through selecting the largest happiness values at each step, the utilization of the heap data structure significantly enhances efficiency compared to alternative methods like sorting the happiness array that we did in first approach. \n\n### \uD83D\uDCDADetailed Approach:\n1. **Convert the List to a Max Heap:** To efficiently select the children with the highest happiness values, we can use a max heap. However, Python\'s default heap implementation is a min heap. So, we convert the list into a max heap by inverting the happiness values (multiply each value by -1).\n   \n2. **Initialize Variables:** Initialize `total_happiness_sum` to keep track of the sum of happiness values of the selected children. Initialize `turns` to keep track of the number of turns taken.\n\n3. **Iterate for K Turns:** We iterate for k turns, where in each turn, we:\n   - Pop the top element from the max heap. Since we inverted the happiness values initially, popping from the heap gives us the child with the highest original happiness value.\n   - Decrement the happiness value by the number of turns taken so far. This accounts for the decrement in happiness for all unselected children.\n   - Add the happiness value to `total_happiness_sum`. Ensure that negative happiness values are not considered by taking the maximum of 0 and the computed value.\n   - Increment the `turns` variable to prepare for the next iteration.\n\n4. **Return Total Happiness Sum:** After k turns, return the total happiness sum, which represents the maximum sum of happiness values achievable by selecting k children.\n\n\n<!-- # Complexity\n- \u23F1\uFE0F Time Complexity: `O(n)` where n is the number of pairs in the list.\n\n- \uD83D\uDE80 Space Complexity: `O(n)` for the two lists. -->\n\n# Code\uD83D\uDC69\uD83C\uDFFB\u200D\uD83D\uDCBB:\n```Python []\nclass Solution:\n    def maximumHappinessSum(self, happiness: List[int], k: int) -> int:\n        # Convert the list into a max heap by inverting the happiness values \n        # Python\'s default heap data structure is a min heap\n        max_heap = [-h for h in happiness]\n        heapq.heapify(max_heap)\n        \n        total_happiness_sum = 0\n        turns = 0\n\n        for i in range(k):\n            # Invert again to get the original value\n            total_happiness_sum += max(-heapq.heappop(max_heap) - turns, 0)\n\n            # Increment turns for the next iteration\n            turns += 1\n            \n        return total_happiness_sum\n```\n```Java []\nclass Solution {\n    public long maximumHappinessSum(int[] happiness, int k) {\n        // Create a max heap using PriorityQueue with a custom comparator\n        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());\n\n        // Add all elements to the priority queue\n        for (int h : happiness) {\n            pq.add(h);\n        }\n\n        long totalHappinessSum = 0;\n        int turns = 0;\n\n        for (int i = 0; i < k; i++) {\n            // Add the current highest value to the total happiness sum and remove it from the max heap \n            totalHappinessSum += Math.max(pq.poll() - turns, 0);\n\n            // Increment turns for the next iteration\n            turns++;\n        }\n\n        return totalHappinessSum;\n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    long long maximumHappinessSum(vector<int>& happiness, int k) {\n        // Max heap by default\n        priority_queue<int> pq; \n\n        // Push all the happiness values into the priority queue\n        for(const auto& h: happiness)\n            pq.push(h); \n\n        long long totalHappinessSum = 0;\n        int turns = 0;\n\n        for(int i = 0; i < k; i++) {\n            // Add the current highest value to the total happiness sum\n            totalHappinessSum += max(pq.top() - turns, 0);\n\n            // Remove the highest value after using it\n            pq.pop(); \n\n            // Increment turns for the next iteration\n            turns++; \n        }\n\n        return totalHappinessSum;\n    }\n};\n```\n\n# \uD83D\uDCA1 I invite you to check out [my profile](https://leetcode.com/Mohammed_Raziullah_Ansari/) for detailed explanations and code for each method. Happy coding and learning! \uD83D\uDCDA
['Array', 'Greedy', 'Sorting', 'C++', 'Java', 'Python3']