LeetCode Entry

3066. Minimum Operations to Exceed Threshold Value II

13.02.2025 medium 2025 kotlin rust

Count nums += min(x,y) 2+max(x,y) < k

3066. Minimum Operations to Exceed Threshold Value II medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/894

Problem TLDR

Count nums += min(x,y)*2+max(x,y) < k #medium #heap

Intuition

There is only a heap solution.

Approach

• some small tricks are possible, given resul is guaranteed by rules
• in-place heap is possible

Complexity

• Time complexity: \(O(nlog(n))\)

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

Code

    fun minOperations(nums: IntArray, k: Int): Int {
        val q = PriorityQueue(nums.map { 1L * it })
        while (q.peek() < k) q += q.poll() * 2 + q.poll()
        return nums.size - q.size
    }

    pub fn min_operations(nums: Vec<i32>, k: i32) -> i32 {
        let mut q = BinaryHeap::from_iter(nums.iter().map(|x| -x as i64));
        while let Some(x) = q.pop().filter(|&x| x > -k as i64) {
            let y = q.pop().unwrap(); q.push(x * 2 + y)
        }; (nums.len() - q.len() - 1) as i32
    }

    int minOperations(vector<int>& n, int k) {
        priority_queue<long, vector<long>, greater<>> q(begin(n), end(n));
        while (q.top() < k) {
            auto x = 2 * q.top(); q.pop(); x += q.top(); q.pop();
            q.push(x);
        }
        return size(n) - size(q);
    }