You are given a 0-indexed integer array nums, and an integer k.
In one operation, you can remove one occurrence of the smallest element of nums.
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: 3 Explanation: After one operation, nums becomes equal to [2, 11, 10, 3]. After two operations, nums becomes equal to [11, 10, 3]. After three operations, nums becomes equal to [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 3 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 = 1 Output: 0 Explanation: All elements of the array are greater than or equal to 1 so we do not need to apply any operations on nums.
Example 3:
Input: nums = [1,1,2,4,9], k = 9 Output: 4 Explanation: only a single element of nums is greater than or equal to 9 so we need to apply the operations 4 times on nums.
Constraints:
1 <= nums.length <= 501 <= nums[i] <= 1091 <= k <= 109i such that nums[i] >= k.Sort the array first. Start from the smallest element and keep a count of numbers less than k. Remove these elements until all remaining numbers are >= k, counting the number of operations.
This C solution sorts the array and iterates through it, counting how many elements are less than k. The operation count is the number of elements we need to "remove" to satisfy the condition for all elements >= k.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) if considering in-place sorting; otherwise, it's the space required for the sorting algorithm.
Utilize a min-heap (priority queue) to repeatedly remove the smallest element from the array as long as it is below k. Increment a counter for each removal. This approach can be more efficient for larger datasets, although here n is small.
This Java solution uses a priority queue (min-heap) to efficiently remove the smallest elements. It checks if the top of the queue satisfies the condition, ensuring optimal element removal.
Python
Time Complexity: O(n log n) due to heap operations.
Space Complexity: O(n) for storing elements in the heap.
| Approach | Complexity |
|---|---|
| Sort and Count Approach | Time Complexity: O(n log n) due to sorting. |
| Use a Min-Heap | Time Complexity: O(n log n) due to heap operations. |
Minimum Operations to Exceed Threshold Value II |Easy Explanation | Leetcode 3066 | codestorywithMIK • codestorywithMIK • 5,067 views views
Watch 9 more video solutions →Practice Minimum Operations to Exceed Threshold Value I with our built-in code editor and test cases.
Practice on FleetCode