LC3075. Maximize Happiness of Selected Children

Approach 1: Sorting

class Solution:
    def maximumHappinessSum(self, happiness: List[int], k: int) -> int:
        return functools.reduce(
            lambda acc, pair: acc + max(pair[1] - pair[0], 0),
            enumerate(sorted(happiness, reverse=True)[:k]),
            0
        )

Complexity

Time: $O(nlogn)$
Space: $O(n)$

Approach 2: Heap

Notes

Other Languages