Minimum Operations to Exceed Threshold Value I
EasyPrompt
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 <= 109- The input is generated such that there is at least one index
isuch thatnums[i] >= k.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves first sorting the array. The problem states that we remove the smallest element in each operation. To ensure all remaining elements are at least k, we must remove every element that is smaller than k. By sorting the array, we conveniently group all these elements at the beginning. We can then simply iterate through the sorted array and count how many elements are less than k. This count will be our answer.
Algorithm
- Sort the input array
numsin non-decreasing order. - Initialize a counter,
operations, to zero. - Iterate through the sorted array from the beginning.
- For each element, if it is less than
k, increment theoperationscounter. - If an element is greater than or equal to
k, stop the iteration, as all subsequent elements will also meet the condition. - Return the final count of
operations.
Walkthrough
The algorithm begins by sorting the nums array using a standard sorting algorithm, which typically has a time complexity of O(N log N). Once sorted, all elements less than k will appear before any elements greater than or equal to k. We can then perform a single pass over this sorted array. We initialize a counter for the operations. As we iterate, we check if the current element is less than k. If it is, we increment our operations counter. The moment we find an element that is k or larger, we can immediately stop because all following elements will also be greater than or equal to k due to the sorted nature of the array. The final value of the counter is the minimum number of operations required.
import java.util.Arrays; class Solution { public int minOperations(int[] nums, int k) { // Sort the array in ascending order Arrays.sort(nums); int operations = 0; // Iterate through the sorted array for (int num : nums) { if (num < k) { // This element must be removed operations++; } else { // Since the array is sorted, all subsequent elements are >= k break; } } return operations; }}Complexity
Time
O(N log N)
Space
O(log N) or O(N)
Trade-offs
Pros
The logic is straightforward and directly models the process of removing the smallest elements first.
It is a correct and reliable way to solve the problem.
Cons
The time complexity is dominated by the sorting step, making it less efficient than a linear scan.
It modifies the input array (or requires extra space for a copy), which might not be desirable in some contexts.
Solutions
Solution
class Solution {public int minOperations(int[] nums, int k) { int ans = 0; for (int x : nums) { if (x < k) { ++ans; } } 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.