˛

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 ith 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.

Examples

Example 1:

1
2
3
4
5
6

Input: happiness = [1,2,3], k = 2
Output: 4
Explanation: We can pick 2 children in the following way:
- Pick the child with the happiness value == 3. The happiness value of the remaining children becomes [0,1].
- Pick the child with the happiness value == 1. The happiness value of the remaining child becomes [0]. Note that the happiness value cannot become less than 0.
The sum of the happiness values of the selected children is 3 + 1 = 4.

Example 2:

1
2
3
4
5
6

Input: happiness = [1,1,1,1], k = 2
Output: 1
Explanation: We can pick 2 children in the following way:
- Pick any child with the happiness value == 1. The happiness value of the remaining children becomes [0,0,0].
- Pick the child with the happiness value == 0. The happiness value of the remaining child becomes [0,0].
The sum of the happiness values of the selected children is 1 + 0 = 1.

Example 3:

1
2
3
4
5

Input: happiness = [2,3,4,5], k = 1
Output: 5
Explanation: We can pick 1 child in the following way:
- Pick the child with the happiness value == 5. The happiness value of the remaining children becomes [1,2,3].
The sum of the happiness values of the selected children is 5.

Solution

The objective is to maximize the total happiness sum by selecting children with the highest happiness values. A logical strategy is to prioritize choosing children with the highest happiness values first, considering that the happiness of unselected children decreases over time (and some unselected children can have at minimum 0 happiness).

This is a greedy problem, and we can solve it either using sorting or priority queue.

Video explanation

Here is the video explaining different methods in detail. Please check it out:

Method 1 - Sorting in ascending order and select from end

Algorithm

  1. Sort the happiness array say in ascending order (now most happy kids are at the end)
  2. We start selecting the happiest child from end (as we sorted in ascending order)
  3. Reduce the happiness of next child by number of turns we have taken so far.
  4. Sum up all the happinesses.

Dry Run

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

  1. Sorting the array returns [1,2,3]
  2. As we have sorted in ascending order, we start from end of array for selecting happiest children. Also, we need k elements from end, hence i>=n-k.
  3. We select 3, add to ans and increase turn by 1. (k = 1)
  4. Then we select 2nd last child i.e. 2. We reduce it by 1 which is number of turns. Now, we add 1 to ans. (k = 2 and number of turns = 2)
  5. As we have selected all the happy children, we return the ans.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

public long maximumHappinessSum(int[] happiness, int k) {
	Arrays.sort(happiness);
	long ans = 0;
	int n = happiness.length, j = 0;

	for (int i = n - 1; i >= n - k; i--) {
		ans += Math.max(happiness[i] - j++, 0);
	}

	return ans;        
}

Complexity

  • ⏰ Time complexity: O(n log n) - for sorting and then O(n) for updating ans
  • 🧺 Space complexity: O(1)

Method 2 - Sorting in descending order and select from start

This method is similar to previous method, but just starts solving from the start of the array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

public long maximumHappinessSum(int[] happiness, int k) {
	int n = happiness.length;
	
	Integer[] happinessArr = new Integer[n];
	for(int i = 0; i < n; i++) {
		happinessArr[i] = happiness[i];
	}
	
	Arrays.sort(happinessArr, Collections.reverseOrder());

	long ans = 0;
	int j = 0;
	
	for(int i = 0; i < k; i++) {
		ans += Math.max(happinessArr[i] - j++, 0);  
	}
	
	return ans;
}

Complexity

  • ⏰ Time complexity: O(n log n) - for sorting and then O(n) for updating ans
  • 🧺 Space complexity: O(1)

Method 3 - Using MaxHeap

  1. Create the max-heap pq and all happiness values.
  2. Now, pick up the values from heap and subtract the number of turns j and add to happiness values.
  3. Return the happiness values.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

public long maximumHappinessSum(int[] happiness, int k) {
	PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());

	for (int h : happiness) {
		pq.add(h);
	}

	long ans = 0;
	int j = 0;

	for (int i = 0; i < k; i++) {
		ans += Math.max(pq.poll() - j++, 0);
	}

	return ans
}

Complexity

  • ⏰ Time complexity: O(n log n) - O(n) for creating heap and then O(k log n) for extracting k elements from heap
  • 🧺 Space complexity: O(n)