LeetCode 3075 - Maximize Happiness of Selected Children

LeetCode Problem 3075

Difficulty: 🟡 Medium
Topics: Array, Greedy, Sorting

Solution

Problem Understanding

The problem gives us an array happiness representing the happiness values of n children standing in a queue and asks us to select exactly k children to maximize the sum of their happiness. The twist is that each time we select a child, all unselected children have their happiness decreased by 1, but their happiness cannot go below 0.

In other words, the earlier we select children with higher happiness, the more value we preserve. The input guarantees that happiness[i] is at least 1, k is at least 1, and n can be up to 200,000. This means naive combinatorial approaches that try all possible sequences are infeasible due to exponential growth.

Key points:

• Happiness cannot go negative.
• Order of selection affects remaining happiness values.
• n can be very large, so an O(n^2) approach is too slow.
• k can equal n, in which case all children are selected.

Important edge cases include:

• All happiness values being equal.
• k = 1 or k = n.
• Happiness values being large and n large, testing for integer overflows in Go (int64).

Approaches

Brute Force: Consider every possible sequence of selecting k children. For each sequence, simulate decrementing the happiness of remaining children each turn. Sum the selected happiness. This is correct because it explores all possibilities, but it has a time complexity of O(n! / (n-k)!) which is completely impractical for n up to 200,000. Memory usage could also grow if we attempt to copy arrays repeatedly.

Optimal Approach: The key observation is that to maximize happiness, we should always pick the child with the highest current happiness value first. This is a greedy strategy. Sorting the array in descending order ensures that each pick preserves the largest possible sum. The total decrement effect is captured by the formula happiness[i] - i, where i is the number of previous picks. We clamp this value to 0 because happiness cannot go negative.

The optimal steps are:

1. Sort happiness in descending order.
2. Initialize total = 0.
3. For each of the first k children, compute max(happiness[i] - i, 0) and add it to total.
4. Return total.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n! / (n-k)!)	O(n)	Enumerates all possible sequences of selections, impractical for large n
Optimal	O(n log n)	O(1) or O(n)	Sorts descending and uses greedy selection with linear scan

Algorithm Walkthrough

1. Sort the array: Arrange happiness in descending order. The reasoning is that picking children with higher happiness first preserves more total happiness, since later selections decrease unpicked children's values.
2. Initialize a sum variable: total = 0. This will store the accumulated sum of selected children's happiness.
3. Iterate over the first k elements: For each child at index i (0-based), compute the effective happiness as effective = max(happiness[i] - i, 0). This accounts for the reduction from previous selections, clamped to 0.
4. Accumulate the sum: Add effective to total.
5. Return the result: total now holds the maximum achievable sum.

Why it works: Sorting ensures that at every turn, we pick the child whose happiness will be reduced the least relative to its value. By clamping to zero, we respect the problem’s constraints. This greedy approach produces the optimal sum because any deviation would select a lower value before a higher one, which can only reduce the total sum.

Python Solution

from typing import List

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

In this implementation, we first sort the happiness array in descending order. We then iterate over the first k children, computing the effective happiness after accounting for reductions from previous selections. Each value is clamped to zero to avoid negative happiness. The sum is accumulated and returned.

Go Solution

import "sort"

func maximumHappinessSum(happiness []int, k int) int64 {
    sort.Sort(sort.Reverse(sort.IntSlice(happiness)))
    var total int64 = 0
    for i := 0; i < k; i++ {
        val := happiness[i] - i
        if val < 0 {
            val = 0
        }
        total += int64(val)
    }
    return total
}

Go-specific notes: We use sort.IntSlice with sort.Reverse to sort descending. Since happiness[i] and k can be large, total is declared as int64 to avoid integer overflow. The max operation is implemented with a simple conditional.

Worked Examples

Example 1: happiness = [1,2,3], k = 2

Step	Selected	Remaining	Effective Happiness	Total
0	pick 3	[1,2]	3	3
1	pick 2	[1]	max(2-1,0)=1	4

Output: 4

Example 2: happiness = [1,1,1,1], k = 2

Step	Selected	Remaining	Effective Happiness	Total
0	pick 1	[1,1,1]	1	1
1	pick 1	[1,1]	max(1-1,0)=0	1

Output: 1

Example 3: happiness = [2,3,4,5], k = 1

Step	Selected	Remaining	Effective Happiness	Total
0	pick 5	[2,3,4]	5	5

Output: 5

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates, linear scan over first k is O(k) which is ≤ O(n)
Space	O(1)	In-place sorting, only constant extra variables used

The linear scan after sorting is negligible compared to sorting. Memory usage is minimal because no extra data structures are needed beyond the sorted array.

Test Cases

# Provided examples
assert Solution().maximumHappinessSum([1,2,3], 2) == 4
assert Solution().maximumHappinessSum([1,1,1,1], 2) == 1
assert Solution().maximumHappinessSum([2,3,4,5], 1) == 5

# Boundary cases
assert Solution().maximumHappinessSum([1], 1) == 1  # Single child
assert Solution().maximumHappinessSum([10**8]*5, 5) == sum([10**8 - i for i in range(5)])  # Max happiness values
assert Solution().maximumHappinessSum([5,4,3,2,1], 3) == 5 + 4 + 3  # Already descending

# Edge cases
assert Solution().maximumHappinessSum([1,2,2,3], 2) == 5  # Requires choosing largest first
assert Solution().maximumHappinessSum([1,2,3,4,5], 5) == 15  # Picking all children

Test	Why
Single child	Minimum input size
Maximum happiness	Tests integer overflow handling
Descending already	Confirms sorting is correct
Mixed small values	Checks greedy selection order
Pick all children	Ensures total sum accounts for all decrements correctly

Edge Cases

Case 1: k = 1

When only one child is picked, we should always pick the child with the maximum happiness. This tests whether the algorithm correctly identifies the highest value and does not over-apply decrements.

Case 2: All happiness equal

If all values are equal, selecting any child first may seem arbitrary, but the algorithm must still decrement remaining children and clamp to 0 correctly. This validates that the max(happiness[i] - i, 0) formula works for repeated values.

Case 3: Maximum input size

n = 2*10^5, happiness[i] = 10^8, k = n. This tests performance and integer overflow. The algorithm handles this efficiently because it sorts and iterates linearly, and in Go we explicitly use int64 to prevent overflow.

This solution is fully robust for all inputs under the given constraints.