LeetCode Entry

3075. Maximize Happiness of Selected Children

25.12.2025 medium 2025 kotlin rust

K max values, decreas each pick

3075. Maximize Happiness of Selected Children medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1215

Problem TLDR

K max values, decreas each pick #medium #quickselect

Intuition

Sort and pick K largest.

Approach

• optimize with quickselect
• we still have to sort K items to check 0 overflow

Complexity

• Time complexity: \(O(n + klog(k))\), for optimal; the simplest is O(nlogn)

• Space complexity: \(O(1)\)

Code

// 693ms
    fun maximumHappinessSum(h: IntArray, k: Int) =
        h.sortedDescending().take(k).withIndex().sumOf {(i,h)->max(0,1L*h-i)}

// 12ms
    pub fn maximum_happiness_sum(mut h: Vec<i32>, k: i32) -> i64 {
        h.sort_unstable_by(|a,b|b.cmp(a));
        h.iter().zip(0..k).map(|(h,i)|0.max(h-i)as i64).sum()
    }

// 18ms
    pub fn maximum_happiness_sum(mut h: Vec<i32>, k: i32) -> i64 {
        let (l,m,_) = h.select_nth_unstable_by_key(k as usize-1, |h|-h);
        l.sort_unstable_by(|a,b|b.cmp(a));
        l.iter().chain(once(&*m)).zip(0..).map(|(h,i)|0.max(h-i)as i64).sum()
    }