Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

A child selected after i earlier selections contributes max(0, originalHappiness - i). Choosing larger original values can never reduce a contribution. Selecting them in descending order is also safe: exchanging two out-of-order choices does not decrease their combined contribution, including when values are clamped at zero.

Approach

Sort the happiness values from largest to smallest. For the first k values, add max(0, happiness[i] - i) to the result. The index i is exactly the number of previous selections and therefore the number of decrements this child has experienced.

Stop after k children have been selected and return the total. Values that have fallen to zero contribute nothing, but selecting those remaining children still satisfies the requirement to choose exactly k. The calculation avoids simulating a decrement for every unselected child after each turn.

class Solution:
    def maximumHappinessSum(self, happiness: List[int], k: int) -> int:
        n = len(happiness)
        happiness.sort(reverse = True)
        res = 0

        for i in range(n):
            if k:
                res += max(0, happiness[i] - i)
                k -= 1
            else:
                break

        return res

Complexity analysis

Let n = happiness.length. Time: O(n log n). Auxiliary space: O(n) in the worst case for built-in sorting.