Maximize Happiness of Selected Children - Practice Coding Problems

Maximize Happiness of Selected Children - Problem

You are given an array happiness of length n, and a positive integer k.

There are n children standing in a queue, where the i-th child has happiness value happiness[i]. You want to select k children from these n children in k turns.

In each turn, when you select a child, the happiness value of all the children that have not been selected till now decreases by 1. Note that the happiness value cannot become negative and gets decremented only if it is positive.

Return the maximum sum of the happiness values of the selected children you can achieve by selecting k children.

Input & Output

Example 1 — Basic Case

$ Input: happiness = [1,2,3], k = 2

› Output: 4

💡 Note: Select children with happiness 3 and 2. Child with happiness 3 contributes 3, child with happiness 2 (after 1 decay) contributes 1. Total: 3 + 1 = 4

Example 2 — Larger Array

$ Input: happiness = [1,1,1,1], k = 2

› Output: 1

💡 Note: All children have same happiness. Pick any 2: first contributes 1, second contributes 0 (after 1 decay). Total: 1 + 0 = 1

Example 3 — High Happiness Values

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

› Output: 5

💡 Note: Select the child with maximum happiness 5. No decay affects the selected child. Total: 5

Constraints

1 ≤ n ≤ 2 × 10⁵
1 ≤ k ≤ n
1 ≤ happiness[i] ≤ 10⁸

Visualization

Tap to expand

Understanding the Visualization

Initial State

Children with happiness values [1,2,3], need to select k=2

Greedy Selection

Always pick the child with highest current happiness

Maximum Sum

Optimal selection gives sum = 4

Key Takeaway

🎯 Key Insight: Use greedy strategy - always pick the child with highest current happiness, or mathematically: sort and use formula max(0, happiness[i] - i)

Asked in

G Google 45 a Amazon 38 M Microsoft 32

The key insight is to use a greedy approach - always select the child with highest current happiness. The optimal solution sorts children by happiness and uses the mathematical formula max(0, happiness[i] - i) to calculate the final happiness without simulation. Time: O(n log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy - Always Pick Highest	O(n log n + k²)	O(n)	Sort children by happiness and always pick the happiest available child
Brute Force - Try All Combinations	O(C(n,k) × k)	O(k)	Generate all possible combinations of k children and find the maximum sum
Optimized - Mathematical Formula	O(n log n)	O(1)	Use mathematical insight to avoid simulation - calculate final happiness directly

Greedy - Always Pick Highest — Algorithm Steps

Sort children by happiness in descending order
For k turns, pick the child with highest current happiness
After each pick, decrease happiness of all remaining children by 1
Sum up the happiness values of selected children

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort

Sort children by happiness descending

Pick

Always select child with highest current happiness

Decay

Decrease happiness of remaining children by 1

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

long long solution(int happiness[], int n, int k) {
    int currentHappiness[50];
    int selected[50] = {0};
    long long totalSum = 0;
    
    for (int i = 0; i < n; i++) {
        currentHappiness[i] = happiness[i];
    }
    
    for (int turn = 0; turn < k; turn++) {
        int maxHappiness = -1;
        int bestChild = -1;
        
        // Find child with maximum current happiness among unselected
        for (int i = 0; i < n; i++) {
            if (!selected[i] && currentHappiness[i] > maxHappiness) {
                maxHappiness = currentHappiness[i];
                bestChild = i;
            }
        }
        
        // Select this child
        selected[bestChild] = 1;
        if (currentHappiness[bestChild] > 0) {
            totalSum += currentHappiness[bestChild];
        }
        
        // Decrease happiness of all unselected children
        for (int i = 0; i < n; i++) {
            if (!selected[i] && currentHappiness[i] > 0) {
                currentHappiness[i]--;
            }
        }
    }
    
    return totalSum;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int happiness[50];
    int n = 0;
    char* token = strtok(line, "[],\n ");
    while (token != NULL) {
        happiness[n++] = atoi(token);
        token = strtok(NULL, "[],\n ");
    }
    
    int k;
    scanf("%d", &k);
    
    long long result = solution(happiness, n, k);
    printf("%lld\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n + k²)

O(n log n) for sorting, O(k²) for k selections with k updates each

⚡ Linearithmic

Space Complexity

O(n)

Extra array to track happiness values and selection status

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy - Always Pick Highest — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler