# Maximize Happiness of Selected Children
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximize-happiness-of-selected-children)
Canonical: https://scaleengineer.com/dsa/problems/maximize-happiness-of-selected-children
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## Problem
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
## Naive Simulation
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.
**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.
**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.
### Explanation
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.

```java
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.
### Algorithm
- 1. Convert the input array `happiness` into a mutable list, for instance, an `ArrayList`.
- 2. Initialize a variable `totalHappiness` to 0.
- 3. Loop `k` times to simulate the `k` turns.
- 4. 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.
- 5. After `k` turns, return `totalHappiness`.

## Greedy Approach with Sorting
A more efficient approach comes from a greedy strategy. We can observe that to maximize the total happiness, we should always prioritize selecting children with the highest initial happiness. The penalty for selecting a child later is fixed by the turn number. By sorting the `happiness` array, we can easily pick the top `k` children in an optimal sequence (from highest initial happiness to lowest).
**Time:** O(n log n), dominated by the time it takes to sort the entire `happiness` array. The subsequent loop runs at most `k` times, which is `O(k)`. · **Space:** O(log n) or O(n), depending on the implementation of the sorting algorithm. Java's `Arrays.sort` for primitives uses a variant of quicksort, which has an average space complexity of `O(log n)`.
**Pros:** Significantly more efficient than the naive simulation.; Correct and guaranteed to pass within the given constraints.; Simple to implement using standard library sorting functions.
**Cons:** Sorting the entire array is `O(n log n)`, which can be suboptimal if `k` is much smaller than `n`.
### Explanation
The logic is that the total sum we want to maximize is `(h_1 - 0) + (h_2 - 1) + ... + (h_k - (k-1))`, where `h_1, h_2, ..., h_k` are the initial happiness values of the selected children. To make this sum as large as possible, we must assign the largest happiness values to the terms with the smallest subtractions. This is achieved by picking the child with the highest initial happiness at turn 0, the second-highest at turn 1, and so on.

This leads to a simple algorithm: sort the array and iterate through the `k` largest elements, calculating their contribution at each turn.

```java
import java.util.Arrays;

class Solution {
    public long maximumHappinessSum(int[] happiness, int k) {
        // Sort the array to easily access the children with the highest happiness.
        Arrays.sort(happiness);
        
        long totalHappinessSum = 0;
        int n = happiness.length;
        int turns = 0;
        
        // Iterate from the child with the highest happiness.
        for (int i = n - 1; i >= n - k; i--) {
            // Calculate the current happiness of the child.
            // It decreases by 1 for each turn that has passed.
            long currentHappiness = happiness[i] - turns;
            
            // If the happiness is positive, add it to the sum.
            if (currentHappiness > 0) {
                totalHappinessSum += currentHappiness;
            } else {
                // If the current happiness is not positive, the happiness of the
                // remaining children (which is less than or equal to the current one)
                // will also not be positive after decrementing. So we can stop early.
                break;
            }
            
            // Increment the number of turns for the next child.
            turns++;
        }
        
        return totalHappinessSum;
    }
}
```
### Algorithm
- 1. The key insight is that the total happiness is maximized by picking the children with the highest initial happiness values first.
- 2. The happiness contributed by a child selected at `turn` `i` (0-indexed) is `initial_happiness - i`.
- 3. To maximize the sum, we should pair the largest `initial_happiness` with the smallest decrement (`i=0`), the second largest with the next smallest (`i=1`), and so on.
- 4. Sort the `happiness` array in ascending order.
- 5. Initialize `totalHappiness` (as a `long` to prevent overflow) to 0 and `turns` to 0.
- 6. Iterate from the end of the sorted array for `k` elements (from index `n-1` down to `n-k`).
- 7. In each step, calculate the effective happiness: `happiness[i] - turns`.
- 8. If the effective happiness is positive, add it to `totalHappiness`. Otherwise, we can stop, as subsequent children will yield no happiness.
- 9. Increment `turns` and continue to the next child.
- 10. Return `totalHappiness`.

## Optimized Greedy Approach with a Max-Heap
This approach refines the greedy strategy by using a more suitable data structure. Since we only need to repeatedly find the maximum of the remaining elements, a max-heap is a perfect fit. It avoids the cost of fully sorting the array, which is unnecessary if we only select a small subset of children (`k << n`).
**Time:** O(n + k log n). Building the heap by adding `n` elements one by one takes `O(n log n)`. A more optimized build (e.g., `addAll` from a collection) takes `O(n)`. Then, we perform `k` poll operations, each taking `O(log n)` time. · **Space:** O(n) to store the `n` elements in the `PriorityQueue`.
**Pros:** Asymptotically more efficient than sorting, with a time complexity of `O(n + k log n)`.; Particularly effective when `k` is much smaller than `n`.
**Cons:** Requires `O(n)` extra space for the heap, whereas an in-place sort might use less.; The constant factors for heap operations might be higher than for a highly optimized array sort, potentially making it slower in practice unless `k` is significantly smaller than `n`.
### Explanation
A max-heap allows us to find the maximum element in `O(1)` time (peeking) and remove it in `O(log n)` time. We can build a heap from the `n` happiness values in `O(n)` time. Then, we perform `k` extractions, each taking `O(log n)` time. This leads to a total time complexity that is better than full sorting when `k` is small.

```java
import java.util.Collections;
import java.util.PriorityQueue;

class Solution {
    public long maximumHappinessSum(int[] happiness, int k) {
        // Create a max-heap to store happiness values.
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        for (int h : happiness) {
            maxHeap.add(h);
        }
        
        long totalHappinessSum = 0;
        int turns = 0;
        
        for (int i = 0; i < k; i++) {
            // Get the child with the current maximum happiness.
            int maxHappiness = maxHeap.poll();
            
            // Calculate their happiness at the moment of selection.
            long currentHappiness = maxHappiness - turns;
            
            if (currentHappiness > 0) {
                totalHappinessSum += currentHappiness;
            } else {
                // If the highest happiness child gives 0 or less, the rest will too.
                break;
            }
            
            turns++;
        }
        
        return totalHappinessSum;
    }
}
```
### Algorithm
- 1. The underlying greedy strategy is the same: pick the `k` children with the highest initial happiness.
- 2. Instead of sorting the whole array, use a max-heap (in Java, a `PriorityQueue` with a reverse order comparator) to efficiently access the maximum element.
- 3. Build the max-heap from all the `happiness` values. This can be done in `O(n)` time.
- 4. Initialize `totalHappiness` to 0 and `turns` to 0.
- 5. Loop `k` times:
    - a. Extract the maximum element (`h`) from the heap.
    - b. Calculate the effective happiness: `h - turns`.
    - c. If it's positive, add it to `totalHappiness`.
    - d. If it's zero or less, break the loop early for the same reason as in the sorting approach.
    - e. Increment `turns`.
- 6. Return `totalHappiness`.

# Solutions
### Java

```java
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;
  }
}

```

### Python

```python
class Solution:
    def maximumHappinessSum(self, happiness: List[int], k: int) -> int: happiness . sort(reverse=True) ans = 0 for i, x in enumerate(happiness[: k]): x -= i ans += max(x, 0) return ans

```

### CPP

```cpp
class Solution {
public:
  long long maximumHappinessSum(vector<int> &happiness, int k) {
    sort(happiness.rbegin(), happiness.rend());
    long long ans = 0;
    for (int i = 0, n = happiness.size(); i < k; ++i) {
      int x = happiness[i] - i;
      ans += max(x, 0);
    }
    return ans;
  }
};

```