Scale Engineer

Maximize Happiness of Selected Children

Med
#2731Time: O(n * k). In each of the `k` turns, we iterate through the list of up to `n` children to find the max and then again to update their values. This results in a quadratic time complexity in the worst case (when `k` is close to `n`).Space: O(n) to store the happiness values in a separate list.
Patterns
Greedy
Algorithms
Sorting
Data structures
Array

Prompt

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 * 105
  • 1 <= happiness[i] <= 108
  • 1 <= k <= n

Approaches

3 approaches with complexity analysis and trade-offs.

This approach directly simulates the process described in the problem. In each of the k turns, we find the child with the highest current happiness, add their happiness to our total, and then update the happiness of all remaining children by decrementing their values by one.

Algorithm

    1. Convert the input array happiness into a mutable list, for instance, an ArrayList.
    1. Initialize a variable totalHappiness to 0.
    1. Loop k times to simulate the k turns.
    1. In each turn:
    • a. Find the child with the maximum current happiness in the list. This requires a linear scan.
    • b. Add this maximum happiness value to totalHappiness.
    • c. Remove the selected child from the list.
    • d. Iterate through all remaining children in the list and decrement their happiness by 1. Ensure no happiness value drops below zero.
    1. After k turns, return totalHappiness.

Walkthrough

The naive simulation involves maintaining a list of the current happiness values of all available children. In a loop that runs k times, we perform three main operations: find the maximum value, remove it, and update the rest. Finding the maximum requires iterating through the list, which takes O(N) time, where N is the current number of children. Removing an element from a list can also take O(N). Finally, updating the N-1 remaining children takes another O(N). Since these operations are nested inside a loop that runs k times, the overall complexity becomes prohibitive for large inputs.

import java.util.ArrayList;import java.util.Collections;import java.util.List; class Solution {    public long maximumHappinessSum(int[] happiness, int k) {        List<Integer> happinessList = new ArrayList<>();        for (int h : happiness) {            happinessList.add(h);        }         long totalHappinessSum = 0;        int turns = 0;         for (int i = 0; i < k; i++) {            if (happinessList.isEmpty()) {                break;            }             // Find and remove the child with max happiness            int maxHappiness = 0;            int maxIndex = -1;            for (int j = 0; j < happinessList.size(); j++) {                if (happinessList.get(j) > maxHappiness) {                    maxHappiness = happinessList.get(j);                    maxIndex = j;                }            }                        if (maxIndex == -1) { // All remaining happiness are 0                 // Find any element to remove                 if(!happinessList.isEmpty()) maxIndex = 0;                 else break;            }             totalHappinessSum += happinessList.get(maxIndex);            happinessList.remove(maxIndex);             // Update happiness of remaining children            for (int j = 0; j < happinessList.size(); j++) {                if (happinessList.get(j) > 0) {                    happinessList.set(j, happinessList.get(j) - 1);                }            }        }         return totalHappinessSum;    }}

Note: The provided simulation code is not fully correct because it decrements happiness values based on their current value, not their value at the start of the turn. A correct simulation is more complex, but any direct simulation will face the same performance issues. The greedy approach is the way to go.

Complexity

Time

O(n * k). In each of the `k` turns, we iterate through the list of up to `n` children to find the max and then again to update their values. This results in a quadratic time complexity in the worst case (when `k` is close to `n`).

Space

O(n) to store the happiness values in a separate list.

Trade-offs

Pros

  • Conceptually simple and easy to understand as it directly follows the problem statement.

Cons

  • Extremely inefficient due to repeated linear scans of the list.

  • The time complexity of O(n*k) makes it too slow for the given constraints, leading to a 'Time Limit Exceeded' error on most platforms.

Solutions

class Solution {public  long maximumHappinessSum(int[] happiness, int k) {    Arrays.sort(happiness);    long ans = 0;    for (int i = 0, n = happiness.length; i < k; ++i) {      int x = happiness[n - i - 1] - i;      ans += Math.max(x, 0);    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem