3075. Maximize Happiness of Selected Children LeetCode Solution
In this guide, you will get 3075. Maximize Happiness of Selected Children LeetCode Solution with the best time and space complexity. The solution to Maximize Happiness of Selected Children problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Maximize Happiness of Selected Children
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.
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 * 105
1 <= happiness[i] <= 108
1 <= k <= n
Complexity Analysis
Time Complexity: O(\texttt{sort})
Space Complexity: O(\texttt{sort})
3075. Maximize Happiness of Selected Children LeetCode Solution in C++
class Solution {
public:
long long maximumHappinessSum(vector<int>& happiness, int k) {
long ans = 0;
int decremented = 0;
ranges::sort(happiness, greater<>());
for (int i = 0; i < k; ++i) {
ans += max(0, happiness[i] - decremented);
++decremented;
}
return ans;
}
}; /* code provided by PROGIEZ */
3075. Maximize Happiness of Selected Children LeetCode Solution in Java
class Solution {
public long maximumHappinessSum(int[] happiness, int k) {
final int n = happiness.length;
long ans = 0;
int decremented = 0;
Arrays.sort(happiness);
for (int i = n - 1; i >= n - k; --i) {
ans += Math.max(0, happiness[i] - decremented);
++decremented;
}
return ans;
}
} // code provided by PROGIEZ
3075. Maximize Happiness of Selected Children LeetCode Solution in Python
class Solution:
def maximumHappinessSum(self, happiness: list[int], k: int) -> int:
ans = 0
decremented = 0
happiness.sort(reverse=True)
for i in range(k):
ans += max(0, happiness[i] - decremented)
decremented += 1
return ans # code by PROGIEZ
