Maximize Happiness of Selected Children

Maximize Happiness of Selected Children

What is this problem about?

In this problem, you are given an array of integers representing the happiness values of various children. You must select exactly k children. However, every time you select a child, the happiness of all unselected children strictly decreases by 1 (it cannot drop below 0). Your goal is to maximize the sum of the happiness values of the k selected children.

Why is this asked in interviews?

This is a straightforward Greedy sorting problem. It acts as an excellent screener to see if a candidate can optimize a sequential simulation. Candidates who try to physically subtract 1 from the remaining array after every selection will write slow, $O(N \times K)$ code. Interviewers want to see the mathematical realization that the "turn number" perfectly dictates the deduction amount.

Algorithmic pattern used

The best approach is the Sorting and Greedy pattern.

1. To maximize happiness, you should always pick the children with the highest initial happiness first. Sort the array in descending order.
2. The first child you pick decreases by 0. The second child you pick decreases by 1 (because one turn has passed). The third decreases by 2, and so on.
3. Iterate i from 0 to k-1. The happiness you gain from the i-th child is max(0, sorted_array[i] - i). Add this to your total sum.

Example explanation

Happiness array: [1, 2, 3], k = 2.

1. Sort descending: [3, 2, 1].
2. Turn 0 (i = 0): Pick the first child (3). Deduction is 0. Total = 3.
3. Turn 1 (i = 1): Pick the second child (2). Deduction is 1. We gain 2 - 1 = 1. Total = $3 + 1 = 4$. We picked 2 children. The maximum happiness is 4.

What if the array was [2, 2, 2], k = 3?

• i = 0: Pick 2. Total = 2.
• i = 1: Pick 2. Deduction 1. Gain = 1. Total = 3.
• i = 2: Pick 2. Deduction 2. Gain = 0. Total = 3. Max happiness is 3.

Common mistakes candidates make

A common mistake is physically simulating the degradation by looping through the array and decrementing the values. This is unnecessary and heavily degrades performance. Another mistake is forgetting the floor limit of 0. If a child's happiness is 1 and they are picked on turn 3, their happiness is max(0, 1 - 3) = 0, not -2. Adding negative values to the total sum will yield the wrong answer. Finally, ensure your total sum variable is a long (or 64-bit integer), as the sum of large happiness values can easily exceed standard 32-bit limits.

Interview preparation tip

For the Maximize Happiness of Selected Children interview question, always frame sequential degradation as a mathematical offset based on the loop index i. Whenever a problem states "every turn, all remaining items lose X value", you can almost always sort the items and evaluate them as value - (turn_index * X), completely avoiding nested loops and state mutation.