Problem Description

You have an array happiness of length n representing the happiness values of n children standing in a queue. You need to select exactly k children from this queue to maximize the total happiness sum.

The selection process works as follows:

• You select children one by one over k turns
• When you select a child in any turn, you add their current happiness value to your total
• After each selection, all remaining unselected children have their happiness values decreased by 1
• Happiness values cannot go below 0 (if a child's happiness would become negative, it stays at 0)

For example, if you have children with happiness [5, 3, 2] and you select the first child (happiness = 5), the remaining children's happiness becomes [2, 1] (each decreased by 1).

Your goal is to find the maximum possible sum of happiness values you can achieve by strategically selecting k children.

The solution uses a greedy approach: sort the children by happiness in descending order and select them in that order. When selecting the i-th child (0-indexed), their contribution to the total will be max(happiness[i] - i, 0) because i represents how many selections have already been made before this child.

Intuition

The key insight is that every time we select a child, all remaining children lose 1 happiness point. This creates a "decay effect" - the longer a child waits to be selected, the more their happiness decreases.

To maximize our total, we want to minimize the impact of this decay. Think about it this way: if we have a child with happiness 10 and another with happiness 3, which should we select first? If we select the child with happiness 3 first:

• We get 3 points immediately
• The child with happiness 10 becomes 9 for the next turn
• Total: 3 + 9 = 12

But if we select the child with happiness 10 first:

• We get 10 points immediately
• The child with happiness 3 becomes 2 for the next turn
• Total: 10 + 2 = 12

Wait, they're the same? Not quite! Consider a third child with happiness 7. If we pick in order 3, 10, 7:

• Turn 1: Get 3, others become [9, 6]
• Turn 2: Get 9, other becomes [5]
• Turn 3: Get 5
• Total: 3 + 9 + 5 = 17

But if we pick in order 10, 7, 3:

• Turn 1: Get 10, others become [6, 2]
• Turn 2: Get 6, other becomes [1]
• Turn 3: Get 1
• Total: 10 + 6 + 1 = 17

Still the same? Let's try 10, 7, 3 with initial values [10, 8, 2]:

• Picking 2, 10, 8: Total = 2 + 9 + 6 = 17
• Picking 10, 8, 2: Total = 10 + 7 + 0 = 17

Actually, the order matters when happiness values can drop to 0! Children with lower initial happiness are more vulnerable to becoming 0 if they wait. By selecting children with higher happiness first, we "save" their larger values before decay affects them, and let the smaller values decay (which matters less since they contribute less anyway).

This naturally leads to the greedy strategy: sort by happiness descending and pick in that order. The i-th selected child will have waited through i selections, so their contribution is max(happiness[i] - i, 0).

Learn more about Greedy and Sorting patterns.

Solution Approach

The solution implements the greedy strategy we identified through the following steps:

Step 1: Sort the happiness array in descending order

happiness.sort(reverse=True)

This ensures we process children with higher happiness values first. Sorting takes O(n log n) time.

Step 2: Select the first k children and calculate their contributions

ans = 0
for i, x in enumerate(happiness[:k]):
    x -= i
    ans += max(x, 0)

We iterate through the first k elements of the sorted array. For each child at index i:

• i represents how many children we've already selected (0-indexed)
• This means i turns have passed, so all remaining children have lost i happiness points
• The current child's actual happiness when selected is happiness[i] - i
• We use max(x, 0) to ensure we don't add negative values (happiness can't go below 0)
• We accumulate the sum in ans

Time Complexity: O(n log n) for sorting, plus O(k) for the iteration, giving us O(n log n) overall.

Space Complexity: O(1) if we don't count the space used by sorting (which is typically O(log n) for the sorting algorithm's recursion stack).

Example walkthrough: If happiness = [5, 3, 2, 1] and k = 3:

1. After sorting: [5, 3, 2, 1]
2. Select child 0: happiness = 5 - 0 = 5, sum = 5
3. Select child 1: happiness = 3 - 1 = 2, sum = 5 + 2 = 7
4. Select child 2: happiness = 2 - 2 = 0, sum = 7 + 0 = 7

The maximum happiness sum is 7.

Example Walkthrough

Let's walk through a concrete example with happiness = [4, 6, 1, 5] and k = 3.

Initial Setup:

• We have 4 children with happiness values: [4, 6, 1, 5]
• We need to select exactly 3 children
• Remember: each time we select a child, all unselected children lose 1 happiness point

Step 1: Sort in descending order After sorting: [6, 5, 4, 1]

This greedy ordering ensures we "save" the highest values from decay.

Step 2: Process selections

Selection 1 (i=0):

• Select child with happiness 6
• Since this is the first selection (i=0), no decay has occurred yet
• Contribution: 6 - 0 = 6
• Running sum: 6
• Remaining children's happiness after this selection: [4, 3, 0] (each decreased by 1)

Selection 2 (i=1):

• Select child with original happiness 5
• One selection has already occurred (i=1), so this child has experienced 1 turn of decay
• Contribution: 5 - 1 = 4
• Running sum: 6 + 4 = 10
• Remaining children's happiness after this selection: [2, -1] → [2, 0] (capped at 0)

Selection 3 (i=2):

• Select child with original happiness 4
• Two selections have already occurred (i=2), so this child has experienced 2 turns of decay
• Contribution: 4 - 2 = 2
• Running sum: 10 + 2 = 12

Final Result: Maximum happiness sum = 12

Notice how the formula max(happiness[i] - i, 0) elegantly captures the decay effect: each child at position i in our sorted array will have waited through i selections before being chosen, losing i happiness points in the process.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n + k)

• The sort() operation with reverse=True takes O(n × log n) time, where n is the length of the happiness array
• The iteration through the first k elements takes O(k) time
• Each operation inside the loop (subtraction, max comparison, and addition) takes O(1) time
• Therefore, the total time complexity is O(n × log n + k)

Space Complexity: O(log n)

• The sorting algorithm (Timsort in Python) uses O(log n) space for the recursion stack in the worst case
• The slicing operation happiness[:k] creates an iterator in the enumerate function, which doesn't create a new list
• The variables ans, i, and x use constant O(1) space
• Therefore, the total space complexity is O(log n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Not Handling Negative Happiness Values

The Problem: A common mistake is forgetting to handle cases where happiness values become negative after decrements. If you simply add happiness[i] - i without checking if it's negative, you'll get an incorrect (lower) result.

Incorrect Implementation:

def maximumHappinessSum(self, happiness: List[int], k: int) -> int:
    happiness.sort(reverse=True)
    total = 0
    for i in range(k):
        total += happiness[i] - i  # Wrong! This can subtract when happiness goes negative
    return total

Why It's Wrong: If happiness = [2, 1, 1] and k = 3:

• Select child 0: 2 - 0 = 2
• Select child 1: 1 - 1 = 0
• Select child 2: 1 - 2 = -1 (incorrectly subtracts 1 from total)

Correct Solution: Always use max(happiness[i] - i, 0) to ensure non-negative contributions.

Pitfall 2: Early Termination When Encountering Zero Happiness

The Problem: Some might think they should stop selecting children once the adjusted happiness becomes 0, but this could miss opportunities if later children have high enough initial happiness values.

Incorrect Implementation:

def maximumHappinessSum(self, happiness: List[int], k: int) -> int:
    happiness.sort(reverse=True)
    total = 0
    selected = 0
    for i, h in enumerate(happiness):
        if selected >= k:
            break
        adjusted = h - i
        if adjusted <= 0:
            break  # Wrong! Should continue checking remaining children
        total += adjusted
        selected += 1
    return total

Why It's Wrong: This breaks too early. Even if one child's adjusted happiness is 0, the next child in the sorted order might still have positive adjusted happiness if their initial value is high enough.

Correct Solution: Always iterate through exactly k children (or all children if fewer than k exist) and use max(adjusted, 0) for each.

Pitfall 3: Modifying the Original Array During Selection

The Problem: Attempting to actually modify the happiness array during selection to reflect the decrements, which complicates the logic unnecessarily.

Incorrect Implementation:

def maximumHappinessSum(self, happiness: List[int], k: int) -> int:
    total = 0
    for _ in range(k):
        max_idx = happiness.index(max(happiness))
        total += happiness[max_idx]
        happiness.pop(max_idx)
        # Decrement all remaining children
        for i in range(len(happiness)):
            happiness[i] = max(0, happiness[i] - 1)
    return total

Why It's Wrong: This approach has O(k*n) time complexity due to repeated max finding and array modifications, and the logic becomes unnecessarily complex.

Correct Solution: Sort once at the beginning and calculate the effective happiness value using the index (which represents the number of prior selections) without modifying the array.