Minimum Operations to Exceed Threshold Value II

Med

#2722Time: O(N^2 log N), where N is the initial number of elements. The loop can run up to N-1 times. In each iteration, we sort a list of size roughly N, which takes O(N log N) time. This leads to a total complexity of O(N * N log N), which is too slow for the given constraints.Space: O(N), where N is the initial number of elements in `nums`. This space is used to store the numbers in a dynamic list.1 company

Data structures

Array Heap (Priority Queue)

Companies

tcs

Prompt

You are given a 0-indexed integer array nums, and an integer k.

You are allowed to perform some operations on nums, where in a single operation, you can:

Select the two smallest integers x and y from nums.
Remove x and y from nums.
Insert (min(x, y) * 2 + max(x, y)) at any position in the array.

Note that you can only apply the described operation if nums contains at least two elements.

Return the minimum number of operations needed so that all elements of the array are greater than or equal to k.

Example 1:

Input: nums = [2,11,10,1,3], k = 10

Output: 2

Explanation:

In the first operation, we remove elements 1 and 2, then add 1 * 2 + 2 to nums. nums becomes equal to [4, 11, 10, 3].
In the second operation, we remove elements 3 and 4, then add 3 * 2 + 4 to nums. nums becomes equal to [10, 11, 10].

At this stage, all the elements of nums are greater than or equal to 10 so we can stop.

It can be shown that 2 is the minimum number of operations needed so that all elements of the array are greater than or equal to 10.

Example 2:

Input: nums = [1,1,2,4,9], k = 20

Output: 4

Explanation:

After one operation, nums becomes equal to [2, 4, 9, 3].
After two operations, nums becomes equal to [7, 4, 9].
After three operations, nums becomes equal to [15, 9].
After four operations, nums becomes equal to [33].

At this stage, all the elements of nums are greater than 20 so we can stop.

It can be shown that 4 is the minimum number of operations needed so that all elements of the array are greater than or equal to 20.

Constraints:

2 <= nums.length <= 2 * 10⁵
1 <= nums[i] <= 10⁹
1 <= k <= 10⁹
The input is generated such that an answer always exists. That is, after performing some number of operations, all elements of the array are greater than or equal to k.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the process described in the problem. In each step, we sort the current collection of numbers to identify the two smallest. After finding them, we perform the specified operation, update the collection with the new number, and increment our operation count. We repeat this entire process until the smallest number in our collection meets or exceeds the threshold k.

Algorithm

Initialize operations = 0.
Create a List<Long> from the input nums array to handle potentially large numbers and allow for dynamic resizing.
Start a loop that continues as long as the smallest element in the list is less than k.
Inside the loop:
1. Sort the list in non-decreasing order.
2. If the list has fewer than two elements or if its smallest element (at index 0) is already >= k, break the loop.
3. Extract the two smallest elements, x from index 0 and y from index 1.
4. Remove these two elements from the list.
5. Calculate the new value: newValue = x * 2 + y.
6. Add newValue back to the list.
7. Increment the operations counter.
Return the final operations count.

Walkthrough

To implement this, we can use a dynamic array, such as an ArrayList in Java, to store the numbers, as its size will change with each operation. We also need a counter for the number of operations, initialized to zero.

The main logic resides in a loop. In each iteration, we first sort the list. This brings the two smallest elements to the front. We then check if the smallest element (at index 0) is greater than or equal to k. If it is, our goal is achieved, and we can stop. Otherwise, we remove the first two elements, calculate the new value using the formula min(x, y) * 2 + max(x, y), add this new value back to the list, and increment our operation counter. The loop continues until the condition is met.

It's important to use a long data type for the numbers in the list, as the result of the operation min * 2 + max can easily exceed the maximum value of a standard 32-bit integer.

1import java.util.ArrayList;2import java.util.Collections;3import java.util.List;4 5class Solution {6    public int minOperations(int[] nums, int k) {7        List<Long> list = new ArrayList<>();8        for (int num : nums) {9            list.add((long) num);10        }11 12        int operations = 0;13        while (true) {14            Collections.sort(list);15            if (list.isEmpty() || list.get(0) >= k) {16                break;17            }18            if (list.size() < 2) {19                break; // Cannot perform operation20            }21            22            long x = list.remove(0);23            long y = list.remove(0);24            25            long newValue = x * 2 + y;26            list.add(newValue);27            operations++;28        }29        30        return operations;31    }32}

Complexity

Time

O(N^2 log N), where N is the initial number of elements. The loop can run up to N-1 times. In each iteration, we sort a list of size roughly N, which takes O(N log N) time. This leads to a total complexity of O(N * N log N), which is too slow for the given constraints.

Space

O(N), where N is the initial number of elements in `nums`. This space is used to store the numbers in a dynamic list.

Trade-offs

Pros

Conceptually simple and easy to follow.
Direct translation of the problem statement into code.

Cons

Extremely inefficient due to repeated sorting.
Will result in a 'Time Limit Exceeded' (TLE) error on platforms like LeetCode for the given constraints.

A significantly more efficient solution involves using a min-heap, which is perfectly suited for problems that require repeatedly finding and extracting the minimum element from a collection. In Java, this is implemented with the PriorityQueue class. By maintaining the numbers in a min-heap, we can access the smallest element in O(1) time and extract it in O(log N) time, which is a massive improvement over the O(N log N) sorting step in the brute-force approach.

Algorithm

Initialize operations = 0.
Create a min-heap (a PriorityQueue<Long> in Java) and populate it with all elements from the nums array. Using long prevents potential integer overflow.
Start a while loop that continues as long as the heap contains at least two elements and the smallest element (retrieved via peek()) is less than k.
Inside the loop:
1. Extract the two smallest elements, x and y, by calling poll() twice.
2. Calculate the new value: newValue = x * 2 + y. Since x is guaranteed to be the smaller of the two, this is equivalent to min(x, y) * 2 + max(x, y).
3. Add newValue back into the heap using add().
4. Increment the operations counter.
Once the loop terminates, return the total operations count.

Walkthrough

The strategy is to use the greedy approach of always combining the two smallest available numbers. A min-heap makes this strategy highly efficient.

First, we insert all numbers from the input array nums into a min-heap. We must use a PriorityQueue<Long> to avoid integer overflow when calculating the new values. We also initialize an operations counter to zero.

The main logic is a loop that runs as long as the heap's smallest element is less than k and there are at least two elements to combine. Inside the loop, we poll() the two smallest elements, x and y. We then compute the new value x * 2 + y and add() it back to the heap. For each such combination, we increment our operations counter. The heap automatically reorganizes itself to maintain the min-heap property after each insertion.

The loop terminates when the smallest element in the heap is finally greater than or equal to k. At this point, we have performed the minimum number of operations required, and we return the count.

1import java.util.PriorityQueue;2 3class Solution {4    public int minOperations(int[] nums, int k) {5        // Use a min-heap to efficiently find the two smallest elements.6        // Use Long to prevent overflow from the operation.7        PriorityQueue<Long> pq = new PriorityQueue<>();8        for (int num : nums) {9            pq.add((long) num);10        }11 12        int operations = 0;13        // Continue as long as there are at least two elements and the smallest14        // element is less than k.15        while (pq.size() >= 2 && pq.peek() < k) {16            // Get the two smallest elements17            long x = pq.poll();18            long y = pq.poll();19 20            // Perform the operation and add the new element back to the heap21            // Since x was polled first, x <= y, so this is min*2 + max.22            long newValue = x * 2 + y;23            pq.add(newValue);24            25            // Increment the operation count26            operations++;27        }28 29        return operations;30    }31}

Complexity

Time

O(N log N), where N is the number of elements. Initializing the heap by adding N elements one by one takes O(N log N). The `while` loop runs at most N-1 times, and each iteration involves `poll()` and `add()` operations, which take O(log M) time where M is the current heap size (M ≤ N). Thus, the overall time complexity is dominated by these heap operations.

Space

O(N), where N is the number of elements in `nums`. This space is required to store all the numbers in the priority queue.

Trade-offs

Pros

Highly efficient, with a time complexity that passes the problem constraints.
It is the optimal approach for this problem.
The use of a min-heap is a natural fit for the problem's requirement of repeatedly finding the smallest elements.

Cons

Requires knowledge of the Priority Queue data structure.
Slightly higher constant factor overhead compared to a simple array, but this is negligible given the asymptotic improvement.

Solutions

Solution

1class Solution {2public3  int minOperations(int[] nums, int k) {4    PriorityQueue<Long> pq = new PriorityQueue<>();5    for (int x : nums) {6      pq.offer((long)x);7    }8    int ans = 0;9    for (; pq.size() > 1 && pq.peek() < k; ++ans) {10      long x = pq.poll(), y = pq.poll();11      pq.offer(Math.min(x, y) * 2 + Math.max(x, y));12    }13    return ans;14  }15}

1class Solution {2public:3  int minOperations(vector<int> &nums, int k) {4    using ll = long long;5    priority_queue<ll, vector<ll>, greater<ll>> pq;6    for (int x : nums) {7      pq.push(x);8    }9    int ans = 0;10    for (; pq.size() > 1 && pq.top() < k; ++ans) {11      ll x = pq.top();12      pq.pop();13      ll y = pq.top();14      pq.pop();15      pq.push(min(x, y) * 2 + max(x, y));16    }17    return ans;18  }19};

1class Solution:2    def minOperations(self, nums: List[int], k: int) -> int: heapify(nums) ans = 0 while len(nums) > 1 and nums[0] < k: x, y = heappop(nums), heappop(nums) heappush(nums, min(x, y) * 2 + max(x, y)) ans += 1 return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem