Watch 10 video solutions for Maximize Happiness of Selected Children, a medium level problem involving Array, Greedy, Sorting. This walkthrough by codestorywithMIK has 6,459 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an array happiness of length n, and a positive integer k.
There are n children standing in a queue, where the ith child has happiness value happiness[i]. You want to select k children from these n children in k turns.
In each turn, when you select a child, the happiness value of all the children that have not been selected till now decreases by 1. Note that the happiness value cannot become negative and gets decremented only if it is positive.
Return the maximum sum of the happiness values of the selected children you can achieve by selecting k children.
Example 1:
Input: happiness = [1,2,3], k = 2 Output: 4 Explanation: We can pick 2 children in the following way: - Pick the child with the happiness value == 3. The happiness value of the remaining children becomes [0,1]. - Pick the child with the happiness value == 1. The happiness value of the remaining child becomes [0]. Note that the happiness value cannot become less than 0. The sum of the happiness values of the selected children is 3 + 1 = 4.
Example 2:
Input: happiness = [1,1,1,1], k = 2 Output: 1 Explanation: We can pick 2 children in the following way: - Pick any child with the happiness value == 1. The happiness value of the remaining children becomes [0,0,0]. - Pick the child with the happiness value == 0. The happiness value of the remaining child becomes [0,0]. The sum of the happiness values of the selected children is 1 + 0 = 1.
Example 3:
Input: happiness = [2,3,4,5], k = 1 Output: 5 Explanation: We can pick 1 child in the following way: - Pick the child with the happiness value == 5. The happiness value of the remaining children becomes [1,2,3]. The sum of the happiness values of the selected children is 5.
Constraints:
1 <= n == happiness.length <= 2 * 1051 <= happiness[i] <= 1081 <= k <= nProblem Overview: You are given an array where happiness[i] represents the happiness value of the i-th child. When you select a child, their happiness contributes to the total, but every subsequent selection reduces remaining children's happiness by 1. The goal is to choose k children that maximize the final happiness sum.
Approach 1: Sorting + Greedy (O(n log n) time, O(1) extra space)
The key observation: the earlier you select a child, the less their happiness gets reduced. So the children with the largest happiness values should be chosen first. Sort the array in descending order using a sorting technique, then iterate through the first k elements. For the i-th selection, the effective contribution becomes max(happiness[i] - i, 0) because each previous pick decreases remaining happiness by 1. Accumulate these values until you either pick k children or the contribution becomes zero. This greedy ordering guarantees the maximum total happiness.
This works because picking a smaller value earlier would only reduce the contribution of a larger value later. Greedy ordering after sorting ensures the largest possible contributions happen when the reduction factor is smallest. The algorithm primarily uses operations on an array and a greedy decision process.
Approach 2: Hash Map Counting (O(n + U log U) time, O(U) space)
Instead of sorting the full array, you can count frequencies of each happiness value using a hash map. After building the map, process values from highest to lowest and simulate picking children while applying the decreasing penalty. Each time you select a child with value v, the actual contribution becomes v - selected. Continue until k selections are made or contributions drop to zero.
This approach reduces redundant comparisons when many children share the same value. It still follows the same greedy principle: always take the largest available happiness first. The hash structure helps aggregate duplicates and iterate through unique values in descending order.
Recommended for interviews: The sorting + greedy solution is the expected approach. It is simple, easy to reason about, and runs in O(n log n) time with constant extra space. Explaining why picking the largest values first maximizes the sum demonstrates strong greedy intuition. Mentioning the hash map counting variant shows awareness of optimization techniques when duplicates are common.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting + Greedy | O(n log n) | O(1) | General case. Simple and most commonly expected interview solution. |
| Hash Map Counting | O(n + U log U) | O(U) | When many duplicate happiness values exist and you want to process unique values. |