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.
This is the most efficient approach. It correctly deduces that the problem is not about simulating the removal process but simply about counting how many elements need to be removed. To satisfy the condition that all elements are greater than or equal to k, we must remove every single element that is less than k. The number of such elements is precisely the number of operations needed, regardless of the order in which they are removed. Therefore, a single pass through the array to count these elements is sufficient.
Algorithm
- Initialize a counter variable,
operations, to 0. - Iterate through each element
numin the input arraynums. - For each
num, check if it is less than the thresholdk. - If
num < k, increment theoperationscounter. - After iterating through all the elements, return the total
operationscount.
Walkthrough
The key insight for this optimal solution is that the step-by-step removal of the smallest element is a distraction. The final state requires no elements less than k to be present. This means every element that is initially less than k must be removed. The number of operations is therefore simply the count of elements in the original array that are less than k. The algorithm implements this directly: it initializes a counter to zero, iterates through the nums array once, and for each number, it increments the counter if the number is less than k. This avoids any sorting or modification of the array, leading to a linear time complexity and constant space complexity.
class Solution { public int minOperations(int[] nums, int k) { int operations = 0; // Iterate through each number in the array for (int num : nums) { // If the number is less than k, it needs to be removed if (num < k) { operations++; } } return operations; }}Complexity
Time
O(N)
Space
O(1)
Trade-offs
Pros
Achieves optimal time complexity of O(N).
Uses constant extra space, making it memory efficient.
The implementation is extremely simple and concise.
Cons
This approach might seem too simple and overlooks the 'remove the smallest element' part of the problem description, but it correctly identifies the core requirement.
Solutions
Solution
class Solution {public int minOperations(int[] nums, int k) { int ans = 0; for (int x : nums) { if (x < k) { ++ans; } } return ans; }}class Solution {public: int minOperations(vector<int> &nums, int k) { int ans = 0; for (int x : nums) { if (x < k) { ++ans; } } return ans; }};class Solution: def minOperations( self, nums: List[int], k: int) -> int: return sum(x < k for x in nums)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.