Maximize Happiness of Selected Children - Solution & Explanation
Problem Statement
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 <= n
Approach Overview
Problem 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 1: Sorting Approach
This approach involves sorting the input data first and then finding the solution by traversing through the sorted data. This approach is generally straightforward and often leads to a solution by leveraging sorted order, which simplifies many problems, such as finding pairs or detecting duplicates.
This C program sorts the input array using the C standard library's qsort function and prints the sorted elements. You can replace the print operation with the logic required for your problem, like finding pairs or specific elements.
Complexity
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) or O(n), depending on the usage of additional data structures.
Approach 2: Hash Map Approach
This approach leverages a hash map to efficiently solve problems requiring quick lookups or to detect duplicates. This method is optimal for problems where you need to count occurrences or require O(1) average-time complexity for lookups.
This C example uses a simple hash map as an array to count occurrences of each number in the array. This method is useful for frequency counting or detecting duplicates.
Complexity
Time Complexity: O(n)
Space Complexity: O(n) for the hash map.
Approach 3: Greedy + Sorting
To maximize the sum of happiness values, we should prioritize selecting children with higher happiness values. Therefore, we can sort the children in descending order by happiness value, and then select k children in sequence. For the current i-th child, the happiness value obtained is max(happiness[i] - i, 0). Finally, return the sum of happiness values of these k children.
The time complexity is O(n times log n + k), and the space complexity is O(log n), where n is the length of the array happiness.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Sorting Approach | Time Complexity: O(n log n) due to sorting. |
| Hash Map Approach | Time Complexity: O(n) |
| Greedy + Sorting | — |
Detailed Complexity Analysis
| 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. |
Video Solution
Maximize Happiness of Selected Children | Sorting | Max Heap | Leetcode 3075 | codestorywithMIK • codestorywithMIK • 6,740 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Maximize Happiness of Selected Children easy or hard?
Maximize Happiness of Selected Children Python/Java solution
How to solve Maximize Happiness of Selected Children in O(n)?
What is the best approach for Maximize Happiness of Selected Children?
Is Maximize Happiness of Selected Children asked at Google/Amazon/Meta?
What data structure is used in Maximize Happiness of Selected Children?
What is the time complexity of Maximize Happiness of Selected Children?
Ready to solve this problem?
Practice Maximize Happiness of Selected Children with our built-in code editor and test cases.
Practice on FleetCode