Maximize Happiness of Selected Children

main.md

Question

Approach

To solve this, I first sort the happiness array in descending order so that I always consider the children with the highest happiness values first. Since every time I pick a child the happiness of all remaining unpicked children decreases by 1 (but never below 0), the child I pick on the i-th turn (0-indexed) effectively contributes happiness[i] - i to the total. I then iterate through the first k children in the sorted list, reduce each value by its pick index, and add only the positive results to the total (because happiness cannot go negative, haha).

Implementation

class Solution:
    def maximumHappinessSum(self, happiness: List[int], k: int) -> int:
        happiness.sort(reverse=True)
        total = 0
        
        for i in range(k):
            gain = happiness[i] - i
            if gain > 0:
                total += gain
            else:
                break
                
        return total

Complexities

• Time: O(nlogn)
• Space: O(1)