## Table of Contents

Source: https://leetcode.com/problems/maximize-happiness-of-selected-children/description/

## Description: Maximize Happiness of Selected Children

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`

child has ^{th}**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*.

**Example 1**

1 2 3 4 5 6 |
<strong>Input:</strong> happiness = [1,2,3], k = 2 <strong>Output:</strong> 4 <strong>Explanation:</strong> 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 |
<strong>Input:</strong> happiness = [1,1,1,1], k = 2 <strong>Output:</strong> 1 <strong>Explanation:</strong> 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 |
<strong>Input:</strong> happiness = [2,3,4,5], k = 1 <strong>Output:</strong> 5 <strong>Explanation:</strong> 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. |

**Constraints**

`1 <= n == happiness.length <= 2 * 10`

^{5}`1 <= happiness[i] <= 10`

^{8}`1 <= k <= n`

## Solution

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
class Solution { public long maximumHappinessSum(int[] happiness, int k) { //1. sort the array Arrays.sort(happiness); int n = happiness.length; long sum = 0; //to keep trck of the turns int itr = 0; //start from the last child with the happiness greater than all the other childs for(int i=n-1;i>=0;i--){ //if k is 0 return sum if(k==0){ return sum; } if(happiness[i]-itr > 0){ sum+= happiness[i] - itr; //increment turn itr++; } else { return sum; } k--; } return sum; } } |

### Time Complexity

O(nlogn), where n is the size of the array happiness

### Space Complexity

O(log(n)), where n is the size of the array happiness

Note: in java sort is implemented as a variant of quicksort which has space complexity of O(Log (n))

In the case of objects, java is going to use a hybrid between mergesort and insertion sort , called TimSort, which has O(n) space complexity. For primitive types, java will use a dual pivot variation of quicksort, which has O(log(n)) space complexity.