Problem

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.

Examples

Example 1:

1
2
3
4
5
6
7

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:

1
2
3

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:

1
2
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 <= 50
  • 1 <= nums[i] <= 10^9
  • 1 <= k <= 10^9
  • The input is generated such that there is at least one index i such that nums[i] >= k.

Solution

Method 1 - Using Minheap

Since we are constantly dealing with the smallest element, the min-heap becomes a natural choice for this problem. A min-heap allows us to efficiently access and remove the smallest element.

Approach:

  1. Create a Min-Heap:
    • Insert all elements of the array nums into a min-heap.
  2. While Smallest Element < k:
    • Access the smallest element using the heap.
    • If the smallest element is less than k, remove it and increment the operation counter.
  3. Stop Condition:
    • Once the smallest element in the heap is greater than or equal to k, stop, as no more removals are needed.
  4. Edge Cases:
    • If all elements are already >= k at the start, return 0 (no operations needed).
    • If the array becomes empty before all elements satisfy the condition, the task is impossible (this is not explicitly stated in the problem, but it should be checked).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public int minOperations(int[] nums, int k) {
        // Create a min-heap using PriorityQueue
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int num : nums) {
            heap.add(num);  // Insert all elements into the heap
        }

        int ops = 0; // Counter for the number of removals

        while (!heap.isEmpty()) {
            int smallest = heap.poll();  // Remove the smallest element
            if (smallest >= k) {  // If the smallest element meets the condition, stop
                break;
            }
            ops++;  // Increment the operation counter
        }

        return ops;  // Return the total number of operations
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def min_operations(self, nums: List[int], k: int) -> int:
        # Create a min-heap from the input list
        heapify(nums)  # Min-heapify the array in O(n) time
        ops = 0  # Counter for the number of removals

        while nums:
            smallest = heappop(nums)  # Remove the smallest element
            if smallest >= k:  # If the smallest element meets the condition, we're done
                break
            ops += 1  # Increment the operation count

        return ops

Complexity

  • ⏰ Time complexity: O(n log n) - Build heap takes O(n) and then we remove the smaller elements than k, and in worst case we can have n elements that has to removed.
  • 🧺 Space complexity: O(n)

Method 2 - Simply count elements less than k

Another easy way is counting how many elements are less than k, as it iterates through the array and tallies all the elements that fail to meet the condition.

However, it doesn’t actually simulate the removal process, as described in the original problem where elements are continuously removed until all remaining elements are >= k.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    public int minOperations(int[] nums, int k) {
        int count = 0; // Counter for elements less than k
        for (int i = 0; i < nums.length; i++) {
            // If the current number is less than k, increase the counter
            if (nums[i] < k) {
                count++;
            }
        }
        return count; // Return the total count
    }
}
1
2
3
4
5
6
7

class Solution:
    def min_operations(self, nums: list[int], k: int) -> int:
        count = 0  # Counter for elements less than k
        for num in nums:
            if num < k:  # Check if the current number is less than k
                count += 1  # Increment the counter
        return count  # Return the total count

Complexity

  • ⏰ Time complexity: O(n), as we iterate over the list once, where n is the number of elements in nums.
  • 🧺 Space complexity: O(1)