LeetCode Entry

3634. Minimum Removals to Balance Array

06.02.2026 medium 2026 kotlin rust

Min removals to make min k not less than max window

3634. Minimum Removals to Balance Array medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1260

Problem TLDR

Min removals to make min*k not less than max #medium #sliding_window

Intuition

    // 12 18      k=2  wrong answer
    //                 why 0 instead of 1 ?
    //        ok, read description wrong
    //       it k times not k diff
    // another case is int overflow
    // 1 10 10 10 10 20

Invert the problem: maximum window that we want to keep is the answer.

Approach

• lazy sliding window: we don’t have to shrink window, only care about expanding it
• use longs

Complexity

• Time complexity: \(O(nlogn)\)

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

Code

// 41ms
    fun minRemoval(n: IntArray, k: Int) = n.run {
        sort(); var w = 0; count { 1L*it > 1L*k*n[w] && ++w > 0 }
    }

// 9ms
    pub fn min_removal(mut n: Vec<i32>, k: i32) -> i32 {
        n.sort(); let mut w = 0;
        for &x in &n { w += (x as i64 > n[w]as i64*k as i64) as usize}; w as i32
    }